Wikipedia:Reference desk/Mathematics: Difference between revisions
Line 181: | Line 181: | ||
: One interesting thing I noticed is that <math>\frac{n^{k-i} (i+1)!}{\operatorname{C}(k, i-1)}</math> is invariant with respect to <math>k</math>, and starts out <math>1, \frac{1}{2}, 0, -1, 0, 20, 0, -1512, 0, 302400, 0, -131345280, 0, 108972864000, 0, 157661939635200, 0, 371498581149696000...</math>, but I don't see an obvious pattern here and this series isn't in OEIS. [[Special:Contributions/24.255.17.182|24.255.17.182]] ([[User talk:24.255.17.182|talk]]) 22:13, 25 November 2016 (UTC) |
: One interesting thing I noticed is that <math>\frac{n^{k-i} (i+1)!}{\operatorname{C}(k, i-1)}</math> is invariant with respect to <math>k</math>, and starts out <math>1, \frac{1}{2}, 0, -1, 0, 20, 0, -1512, 0, 302400, 0, -131345280, 0, 108972864000, 0, 157661939635200, 0, 371498581149696000...</math>, but I don't see an obvious pattern here and this series isn't in OEIS. [[Special:Contributions/24.255.17.182|24.255.17.182]] ([[User talk:24.255.17.182|talk]]) 22:13, 25 November 2016 (UTC) |
||
:(ec) Express the powers as linear combinations of binomial coefficients and use the [[Hockey-stick identity]]. |
|||
::<math>\sum_{i=1}^n i^k = \sum_{i=1}^n \sum_{m=0}^k a_m \binom i m = \sum_{m=0}^k a_m \sum_{i=1}^n \binom i m = \sum_{m=0}^k a_m \binom {n+1}{m+1}</math> |
|||
:[[User:Bo Jacoby|Bo Jacoby]] ([[User talk:Bo Jacoby|talk]]) 22:24, 25 November 2016 (UTC). |
Revision as of 22:24, 25 November 2016
of the Wikipedia reference desk.
Main page: Help searching Wikipedia
How can I get my question answered?
- Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
- Post your question to only one section, providing a short header that gives the topic of your question.
- Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
- Don't post personal contact information – it will be removed. Any answers will be provided here.
- Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
- Note:
- We don't answer (and may remove) questions that require medical diagnosis or legal advice.
- We don't answer requests for opinions, predictions or debate.
- We don't do your homework for you, though we'll help you past the stuck point.
- We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.
How do I answer a question?
Main page: Wikipedia:Reference desk/Guidelines
- The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.
November 19
Zero uses
In exponentiation, x0 is generally defined as equalling 1, regardless of the value of x. Meanwhile, division by zero yields an undefined result. I don't understand why we can give a value to the first if it's impossible to give a value to the second, so I'm left supposing that we could logically define the result of division by zero as something, but basically we've not. Am I missing something here, something really basic, or am I correct in saying that it's merely a matter of mathematical convention? Nyttend (talk) 14:10, 19 November 2016 (UTC)
- The basic reason is that while there is a way to extend exponentiation for positive integers to allow the exponent to be zero without losing any properties, there is no way to extend division for positive integers to allow the divisor to be zero without losing any properties. Double sharp (talk) 14:13, 19 November 2016 (UTC)
- Division by zero is undefined because it is inconsistent with the essential properties of arithmetic. This is not true of raising numbers to the 0th power; indeed the two have hardly anything in common. --JBL (talk) 14:51, 19 November 2016 (UTC)
- (Above answers are good- trying to use simpler language here.) You are exactly right that you could define division by zero as something, but basically we've not. People can make whatever definitions they want- the question is whether those definitions are useful and have nice properties. One important property is that things be continuous. That means that if 4/0 is allowed, then it should be close to things like 4/0.1 and 4/0.01 since those denominators are close to 0. But you can just check that 4/0.1 = 40, 4/0.01 = 400, which don't seem to get close to any value in particular. Contrast this with exponents- you can check on your calculator that 4^0.1 = 1.148, 4^0.01 = 1.014, 4^0.001 = 1.001 (i'm cutting off digits in the answer). Looking at those values it seems entirely reasonable to define 4^0 = 1, while there seems to be no reasonable definition for 4/0. Staecker (talk) 15:16, 19 November 2016 (UTC)
- When the Indians first discussed zero and negative numbers they had the rule that zero divided by zero was zero. We could have proceeded on that basis just like the rule that 0^0 is 1 and coped with problems in the same way. It really is a matter of convenience, they don't either of them have a good logical value. 0^0 being 1 is very useful to avoid having to write special things in series and it works out as a good value normally. 0/0 having the value 0 is far less useful and would cause lots of problems. However dogmatically saying 0^0 must be one in all circumstances also causes problems particularly in calculus.
And if 0^0 is 1 then 0^(0/2) one or i in complex numbers so i would be another reasonable value - some people choose 0 instead sometimes there.Dmcq (talk) 15:29, 19 November 2016 (UTC)- (Dmcq, 0^(0/2)=(0^0)^(1/2)=1^(1/2)=1. i is the square root of minus one, not the square root of plus one. Bo Jacoby (talk) 16:33, 19 November 2016 (UTC))
- Sorry, silly me, I try and dredge up what I was thinking of. Dmcq (talk) 16:41, 19 November 2016 (UTC)
- (Dmcq, 0^(0/2)=(0^0)^(1/2)=1^(1/2)=1. i is the square root of minus one, not the square root of plus one. Bo Jacoby (talk) 16:33, 19 November 2016 (UTC))
- Have you read Exponentiation#Zero_to_the_power_of_zero? Generally depends on what your area is. Dmcq (talk) 15:45, 19 November 2016 (UTC)
Yes, you are correct in saying that it's a matter of mathematical convention. Neither x/y nor xy are continuous around (x,y)=(0,0). Choose any nonzero number a. Then a=x/y has solutions (x,y)≠(0,0). Just pick any nonzero y and let x=ay. Then choose a such that 0<a<1. Then a=xy has solutions (x,y)≠(0,0). Just pick any positive y and let x=ay–1. So you are not allowed to assume neither that
nor that
as the functions in question are not continuous.
Some programming languages define 0/x=0 for all values of x, even x=0. That is sometimes convenient and sometimes not. Most programming languages and mathematicians define x0=1 for all values of x. This allows the polynomial to be written conveniently as , but it has nothing to do with continuity. Bo Jacoby (talk) 16:27, 19 November 2016 (UTC).
- Aside from when x = 0 (in which case, some convention is chosen), x0=1, ALWAYS. Even the polynomial you gave as example doesn't evaluate properly, otherwise. Earl of Arundel (talk) 17:46, 19 November 2016 (UTC)
- Aside from when x = 0, 0/x = 0 ALWAYS. I guess that's why they originally had 0/0 = 0. Dmcq (talk) 18:58, 19 November 2016 (UTC)
- Quick comments, since I'm at a quick stop while on the road. (1) Thanks for the "simpler language" answer; I understood that it's a contradiction of the basic principles of arithmetic, but seemingly x0 would be too, and yet we defined it. I needed the point about the 4/0, 4.01, 40.01, etc., because it was a simple demonstration of why my idea doesn't particularly make sense. (2) I read the bit about zero to the power of zero; that's why I said x0 is generally defined as equalling 1, because I knew that 00 wasn't 1, and I didn't want to assume that literally everything else0 was equal to 1 (e.g. complex numbers? I really don't understand how they work). (3) Haven't had time to digest the rest of what you all have said here; I'll come back when I get back home. Nyttend (talk) 19:07, 19 November 2016 (UTC)
- Here is another reason why x0 = 1 is good for positive x. xm / xn = xm-n is clearly true for integers m > n: If you multiply x by itself m times and then divide by it n times then you have m-n times left. This is one of the properties we want to remain true for all real m and n. For m = n it gives: xn / xn = xn–n = x0. But we already know xn / xn must be 1. PrimeHunter (talk) 19:32, 19 November 2016 (UTC)
- Excellent example!Earl of Arundel (talk) 20:05, 19 November 2016 (UTC)
- Division by zero is generally consider undefined in mathematics simply because it leads to erroneous results. Consider this popular math trick. Raising a number to the zeroth power, however, IS well-defined and MUST evaluate to one (and yes, even for complex numbers). Not by mere convention, but because mathematical induction tells us so. For example, the decimal number 953 can be re-written as 9*10^2 + 5*10^1 + 3*10^0, which is clearly consistent. Another way to look at is using calculus. Suppose you had the function y = f(x) = 3x, which is of course the same as saying y = 3x^1. Now if you were to plot out the function you'd plainly see that it has a slope of 3. And indeed, if you took the derivative of f (which also tells us the slope of a function at any given point) you'd get f'(x) = (1*3)x^(1-1) = 3x^0 = 3. Which make sense, since the graph of f is just a straight line, the derivative should thus be a constant value. The only problem we have then is the fact that raising a number to zero doesn't make "arithmetic" sense (in terms of repeated multiplication, that is). To that end, you just have to delve a little deeper. For that, I'd recommend empty product as a starting point. Earl of Arundel (talk) 19:49, 19 November 2016 (UTC)
- One has to be careful to look at a whole picture rather than just trying to find things which confirm what one likes. Dmcq (talk) 20:08, 19 November 2016 (UTC)
- I'm sorry, were you trying to make a point? If so, then please give an example of a case where that doesn't hold. Earl of Arundel (talk) 20:23, 19 November 2016 (UTC)
- Once again, thanks for the assistance. I was aware of silliness like 1=0, 2=1, etc., and their dependence on division by zero, but I couldn't get beyond that, and the significance of issues such as 9*10^2 + 5*10^1 + 3*10^0 never occurred to me. So in other words, we didn't simply define x0 as =1 — had I realised that, I would have been much less confused. Thanks again! Nyttend (talk) 06:09, 20 November 2016 (UTC)
- The subtlety here is that there are different functions called "exponentiation". The repeated-multiplication version, xn where x is, say, a real or complex number, and the n is a natural number, very naturally takes the value x0=1 for all x (real or complex as the case may be).
- On the other hand, the function that sends a pair (x,y) of real or complex numbers to xy is quite a different matter. This is really a different function; conceptually it has nothing to do with repeated multiplication. It is usually defined as xy=ey log x, where the e-to-the part is defined in various ways (inverse of the natural logarithm, for example, or the sum of a power series, or by a differential equation).
- For that kind of exponentiation on the real numbers, typically you define it only for positive values of x, because nonpositive values don't have a logarithm. In the complex numbers, there's more flexibility, but 0 still doesn't have a logarithm. --Trovatore (talk) 07:04, 20 November 2016 (UTC)
- Okay, so how about a concrete example of one of these functions raised to the zeroth power not evaluating to unity? Earl of Arundel (talk) 14:23, 20 November 2016 (UTC)
- (e^(-1/x^2))^x for real x. --JBL (talk) 15:24, 20 November 2016 (UTC)
- I'm not sure what you mean by that. The first exponent can't evaluate to zero because that itself would imply division by zero, which of course nullifies any meaningfulness of the second exponent. I'm looking for some function g(x)^0 that does not map to unity. Something that could be readily demonstrated on Wolfram would be helpful too. Earl of Arundel (talk) 16:26, 20 November 2016 (UTC)
- The function e^(-1/x^2), extended to have the value 0 at x = 0, is smooth (infinitely differentially everywhere) on the real line; it is a standard example of a smooth but not analytic function. Any computer algebra system, including w-a, should be able to handle it easily. --JBL (talk) 16:31, 20 November 2016 (UTC)
- You still haven't addressed the division-by-zero issue. At any rate, the interpretation of 0^0 is, again, dependent on some convention. I understand that. I was specifically referring to any given g(x) that does not itself evaluate to zero. Or am I missing something? Earl of Arundel (talk) 17:24, 20 November 2016 (UTC)
- How do you feel about 5x/x as x tends to zero? What is wrong with simply saying 0/0 is 0 and therefor 5x/x is 5 except at 0 where it is 0? This is what I mean by confirmation bias which is something one really has to avoid in mathematics. Dmcq (talk) 16:47, 20 November 2016 (UTC)
- This has nothing to do with limits. Any non-zero x is going to yield a non-zero quotient. And we cannot "simply say" that 0/0 is 0 because division by zero is undefined (unless some ad hoc convention is being used, as with riemann spheres). Earl of Arundel (talk) 17:24, 20 November 2016 (UTC)
- There's nothing ad-hoc about the Riemann sphere. --Trovatore (talk) 23:19, 20 November 2016 (UTC)
- Exactly why is what you said about exponentiation different from the case for division? Dmcq (talk) 17:57, 20 November 2016 (UTC)
- How is it not? You're comparing apples with oranges. If I'm mistaken, then please express yourself more clearly, because at this point your comments are beginning to sound a bit like nonsense, frankly. Earl of Arundel (talk) 18:14, 20 November 2016 (UTC)
- If it is so easy then gave a difference. Dmcq (talk) 00:20, 21 November 2016 (UTC)
- How is it not? You're comparing apples with oranges. If I'm mistaken, then please express yourself more clearly, because at this point your comments are beginning to sound a bit like nonsense, frankly. Earl of Arundel (talk) 18:14, 20 November 2016 (UTC)
- This has nothing to do with limits. Any non-zero x is going to yield a non-zero quotient. And we cannot "simply say" that 0/0 is 0 because division by zero is undefined (unless some ad hoc convention is being used, as with riemann spheres). Earl of Arundel (talk) 17:24, 20 November 2016 (UTC)
- The function e^(-1/x^2), extended to have the value 0 at x = 0, is smooth (infinitely differentially everywhere) on the real line; it is a standard example of a smooth but not analytic function. Any computer algebra system, including w-a, should be able to handle it easily. --JBL (talk) 16:31, 20 November 2016 (UTC)
- I'm not sure what you mean by that. The first exponent can't evaluate to zero because that itself would imply division by zero, which of course nullifies any meaningfulness of the second exponent. I'm looking for some function g(x)^0 that does not map to unity. Something that could be readily demonstrated on Wolfram would be helpful too. Earl of Arundel (talk) 16:26, 20 November 2016 (UTC)
- (e^(-1/x^2))^x for real x. --JBL (talk) 15:24, 20 November 2016 (UTC)
- Okay, so how about a concrete example of one of these functions raised to the zeroth power not evaluating to unity? Earl of Arundel (talk) 14:23, 20 November 2016 (UTC)
- Once again, thanks for the assistance. I was aware of silliness like 1=0, 2=1, etc., and their dependence on division by zero, but I couldn't get beyond that, and the significance of issues such as 9*10^2 + 5*10^1 + 3*10^0 never occurred to me. So in other words, we didn't simply define x0 as =1 — had I realised that, I would have been much less confused. Thanks again! Nyttend (talk) 06:09, 20 November 2016 (UTC)
- I'm sorry, were you trying to make a point? If so, then please give an example of a case where that doesn't hold. Earl of Arundel (talk) 20:23, 19 November 2016 (UTC)
- One has to be careful to look at a whole picture rather than just trying to find things which confirm what one likes. Dmcq (talk) 20:08, 19 November 2016 (UTC)
- Here is another reason why x0 = 1 is good for positive x. xm / xn = xm-n is clearly true for integers m > n: If you multiply x by itself m times and then divide by it n times then you have m-n times left. This is one of the properties we want to remain true for all real m and n. For m = n it gives: xn / xn = xn–n = x0. But we already know xn / xn must be 1. PrimeHunter (talk) 19:32, 19 November 2016 (UTC)
- Quick comments, since I'm at a quick stop while on the road. (1) Thanks for the "simpler language" answer; I understood that it's a contradiction of the basic principles of arithmetic, but seemingly x0 would be too, and yet we defined it. I needed the point about the 4/0, 4.01, 40.01, etc., because it was a simple demonstration of why my idea doesn't particularly make sense. (2) I read the bit about zero to the power of zero; that's why I said x0 is generally defined as equalling 1, because I knew that 00 wasn't 1, and I didn't want to assume that literally everything else0 was equal to 1 (e.g. complex numbers? I really don't understand how they work). (3) Haven't had time to digest the rest of what you all have said here; I'll come back when I get back home. Nyttend (talk) 19:07, 19 November 2016 (UTC)
- Aside from when x = 0, 0/x = 0 ALWAYS. I guess that's why they originally had 0/0 = 0. Dmcq (talk) 18:58, 19 November 2016 (UTC)
- If I were to define x/0 as anything, I would define it as ±∞, for non-zero values of x, and 0 if x = 0. This is based on the limits. For any nonzero x value, you approach either +∞, when approaching from one side, or −∞, if approaching from the other side. But, with a 0 value for x, you always have 0, no matter which direction you approach the limit from. Note that this can not be extended to defining x/y, as y approaches zero. There are other methods for that, for example, if x = y, this case is equal to 1. StuRat (talk) 18:54, 20 November 2016 (UTC)
- And if one were to define 0/x as anything it would be 0. This is just like if we were to define x^0 as anything it should be 1 and if we were to define 0^x as anything it should be 0. Dmcq (talk) 00:12, 21 November 2016 (UTC)
- (Dmcq, do you mean to say that 0–1=0 ? Bo Jacoby (talk) 01:02, 22 November 2016 (UTC))
- No I did not say it had any value. I am perfectly happy with 0^0 being defined as 1 in most circumstances particularly where the exponent has to be an integer. I am pointing out that it is a matter of convenience that it is defined and 0/0 is not. However there are circumstances where it is not defined and that is for good reasons too. The article explains the situation quite well and why one is normally a good value for it. Dmcq (talk) 11:40, 22 November 2016 (UTC)
- I asked about 0–1, not 00. Bo Jacoby (talk) 22:23, 22 November 2016 (UTC).
- No I did not say it had any value. Dmcq (talk) 23:33, 22 November 2016 (UTC)
- You did say: "if we were to define 0^x as anything it should be 0". Bo Jacoby (talk) 04:07, 23 November 2016 (UTC).
- I was going to 0 from positive x for which 0^x is defined, I did not assign any value for negative x. I don't have a great need to assign a value to every expression and the 'if' was to indicate I wasn't actually trying to do that for 0^0 either. Dmcq (talk) 09:32, 23 November 2016 (UTC)
- One-sided limits like this are not really that good an approach. If we look at negative x, since 0−x is always 0, 0x is always undefined. So this is really not a good reason to define 00 as 0, since the function is not going to behave any more nicely regardless of what value you pick. There is more of a good reason to say that 00 = 1 because that is more useful in the natural contexts 00 comes up in. Double sharp (talk) 09:41, 23 November 2016 (UTC)
- I am as I have said already twice above quite happy to say 0^0=1 in the contexts the article says are good for it and to leave it undefined when exponentiation would most naturally be defined by exp(y*ln x) as that causes the least problem if a limit might creep in somewhere. Dmcq (talk) 09:53, 23 November 2016 (UTC)
- Why don't you leave (–1)2 undefined too? It is not defined by exp(y*ln x). Bo Jacoby (talk) 05:40, 24 November 2016 (UTC).
- I view it as defined only when the 2 is an integer not a real, so I do not view (-1)^2.0 as defined. It is also defined in the complex domain but of course there are problems when doing powers with complex numbers. And if you want to carp about that I also consider , the limit of 1^n as n goes to infinity, as being 1 if the 1 is an integer and undefined if it is a real even though any finite power can be done by repeated multiplication. Dmcq (talk) 11:12, 24 November 2016 (UTC)
- So you adhere to the Trovatore Conjecture: 0≠0 ? Bo Jacoby (talk) 09:06, 25 November 2016 (UTC).
- The reals are different from integers which are different from the rationals which are different from the complex numbers etc. I view a jug containing the average equivalent of 10 comminuted oranges as quite a different thing from a bag of 10 oranges. Dmcq (talk) 10:33, 25 November 2016 (UTC)
- Do you also consider an empty jug containing zero comminuted oranges as quite a different thing than an empty jug of 0 oranges? Do you know of any programming language that evaluates the expression "0=0.0" to "false"? Bo Jacoby (talk) 14:36, 25 November 2016 (UTC).
- If you just thought for a few seconds about what you were saying I'm sure you could answer your own questions. If a person says that the jug contains no comminuted orange I consider it different from if they say it contains no whole oranges which is different again from saying the jug is empty. Equality checks in computer languages are operations that assume you are doing them for a good reason and they have rules to convert operands to make sense as best they can. In Python for instance the equality test 0==0.0 will yield True, but try 'print ((0 is 0)' and 'print (0 is 0.0)' for instance and you'll get a different answer. Coercing to the same format and getting True when testing for arithmetic equality is different from saying they are the same. Dmcq (talk) 15:30, 25 November 2016 (UTC)
- Well actually the is in Python is like in Java but the trick above works because of an optimization, a better example would be PHP's ===. Dmcq (talk)
- I cannot predict your answers because I think you are wrong. My answer is 'yes' to each of the following calculations, but what is your answer, and why?
- "is 1+4=2+3 ?" yes or no.
- "is 3.1=3.10 ?" yes or no.
- "is 0=0.0 ?" yes or no.
- "is 00=00.0 ?" yes or no.
- Bo Jacoby (talk) 16:25, 25 November 2016 (UTC).
- Why don't you leave (–1)2 undefined too? It is not defined by exp(y*ln x). Bo Jacoby (talk) 05:40, 24 November 2016 (UTC).
- I am as I have said already twice above quite happy to say 0^0=1 in the contexts the article says are good for it and to leave it undefined when exponentiation would most naturally be defined by exp(y*ln x) as that causes the least problem if a limit might creep in somewhere. Dmcq (talk) 09:53, 23 November 2016 (UTC)
- One-sided limits like this are not really that good an approach. If we look at negative x, since 0−x is always 0, 0x is always undefined. So this is really not a good reason to define 00 as 0, since the function is not going to behave any more nicely regardless of what value you pick. There is more of a good reason to say that 00 = 1 because that is more useful in the natural contexts 00 comes up in. Double sharp (talk) 09:41, 23 November 2016 (UTC)
- I was going to 0 from positive x for which 0^x is defined, I did not assign any value for negative x. I don't have a great need to assign a value to every expression and the 'if' was to indicate I wasn't actually trying to do that for 0^0 either. Dmcq (talk) 09:32, 23 November 2016 (UTC)
- You did say: "if we were to define 0^x as anything it should be 0". Bo Jacoby (talk) 04:07, 23 November 2016 (UTC).
- No I did not say it had any value. Dmcq (talk) 23:33, 22 November 2016 (UTC)
- I asked about 0–1, not 00. Bo Jacoby (talk) 22:23, 22 November 2016 (UTC).
- No I did not say it had any value. I am perfectly happy with 0^0 being defined as 1 in most circumstances particularly where the exponent has to be an integer. I am pointing out that it is a matter of convenience that it is defined and 0/0 is not. However there are circumstances where it is not defined and that is for good reasons too. The article explains the situation quite well and why one is normally a good value for it. Dmcq (talk) 11:40, 22 November 2016 (UTC)
- (Dmcq, do you mean to say that 0–1=0 ? Bo Jacoby (talk) 01:02, 22 November 2016 (UTC))
- And if one were to define 0/x as anything it would be 0. This is just like if we were to define x^0 as anything it should be 1 and if we were to define 0^x as anything it should be 0. Dmcq (talk) 00:12, 21 November 2016 (UTC)
If is any real or complex number (or linear operator), and the exponent is a positive integer, then is the product . The empty product is one. So . If the number is nonzero, (or the operator is invertible), then , and . If is a positive real number, then is zero, and is one, and is infinite (or undefined). The discontinuity for is unavoidable. If is positive, and the exponent is any real or complex number (or linear operator), then is , where the exponential function is , and the natural logarithm is the real solution to the equation . Where these definitions overlap they provide the same value for . So . Bo Jacoby (talk) 16:54, 21 November 2016 (UTC).
November 20
Modular inverse without coprime
I'm trying to compute , with a very large number (so computing the numerator without the modulus and then dividing is infeasible). The problem is that is not necessarily coprime to . Is there a way I can use modular inverses here? Or how else can the result be computed? 24.255.17.182 (talk) 17:26, 20 November 2016 (UTC)
- You could evaluate the quotient using a summation series identity, but it isn't particularly efficient. It can, however, be generated rather quickly using a straight-forward textual algorithm (oddly enough!). The basic idea is that the result is almost identical to , except that a value of one appears periodically wherever the digit-position is congruent to 0 mod k. Here's a simple C program to demonstrate the concept using "small" numbers:
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
srand(time(0));
typedef unsigned long long
ulong;
ulong
ulong_max_value = ~(ulong(0)),
ulong_max_digits = log(ulong_max_value) / log(10), // Roughly, anyway
limit = sqrt(ulong_max_digits), // Limit the exponents to prevent overflow
k = (rand() % limit) + 1,
n = (rand() % limit) + 1,
a = pow(10, k * n),
b = pow(10, k),
q = pow(10, (k * n) - k); // Our result will be close to this
char
buffer[ulong_max_digits + 1];
sprintf(buffer, "%llu", (ulong)q);
for(int index = 0; buffer[index] != 0; ++index)
if((index % k) == 0)
buffer[index] = '1'; // Insert digit
printf("10^(%llu * %llu) -1 / 10^%llu -1 = %s\n", (ulong)k, (ulong)n, (ulong)k, buffer);
printf("Verify: %llu\n", (ulong)((a - 1)/(b - 1)));
}
- Assuming your big-number library can handle a number as large as , you could then convert the transformed text back into a number and calculate the modulus with m. Earl of Arundel (talk) 20:16, 20 November 2016 (UTC)
- That's still linear wrt n, I believe- let's say n and m are on the order of 10^18. 24.255.17.182 (talk) 20:53, 20 November 2016 (UTC)
- What, you don't have a few exabytes to work with? Seriously, in that case it sounds like JBL's suggestion (below) would be a much more feasible route. Earl of Arundel (talk) 21:22, 20 November 2016 (UTC)
- That's still linear wrt n, I believe- let's say n and m are on the order of 10^18. 24.255.17.182 (talk) 20:53, 20 November 2016 (UTC)
- Assuming m is small, relatively prime to 10, and you know its prime factorization, expand your fraction as a finite geometric series; by Euler's theorem, the summands are periodic modulo m. --JBL (talk) 20:40, 20 November 2016 (UTC)
- Another(?) approach is to note that is a Lucas sequence, and there are efficient (i.e. log n) ways of computing specific entries in Lucas sequences for a given modulus. --RDBury (talk) 23:16, 20 November 2016 (UTC)
- Oh yeah, duh, it's just a degree 2 linear recurrence. That makes it easy, thanks. 24.255.17.182 (talk) 00:31, 21 November 2016 (UTC)
- To be precise, it is the Lucas U-sequence with and . It is also the sequence of repunits in base 10n. More generally, the repunits in any base b form a Lucas sequence with and . The V-sequence is the sequence of numbers that are 1 more than a power of b. GeoffreyT2000 (talk, contribs) 03:15, 24 November 2016 (UTC)
- Oh yeah, duh, it's just a degree 2 linear recurrence. That makes it easy, thanks. 24.255.17.182 (talk) 00:31, 21 November 2016 (UTC)
Conformal transformation from the disk to the sphere
Is there a name for the conformal transformation from the disc to the sphere? Effectively this is the composition of the conformal transformation from the Poincare disk to the plane with the stereographic projection from the plane to the sphere. -Apocheir (talk) 22:10, 20 November 2016 (UTC)
- I'm a bit confused about what you mean by the transformation from the disk to the the plane. I know there is a transformation from the disk to the half-plane but I don't see how you can get to the full plane without some sort of branch point. --RDBury (talk) 23:33, 20 November 2016 (UTC)
- OK, well let me take a step back: does a conformal transformation from the disc (not plane) to the entire sphere exist? If so, does it have a name? My motivation here is that there does exist an area-preserving transformation from the disc to sphere, called the Lambert azimuthal equal-area projection. (Gauss says with a map between spaces of different curvature, at best you can have conformal or area-preserving (or neither), not both. So I'm wondering if there's a conformal counterpart to the Lambert transformation. -Apocheir (talk) 17:42, 22 November 2016 (UTC)
- No there is no such one to one conformal transformation. One can do it between the sphere and the plane (ignoring one point) but there is no such map between a disc and the plane,. One can though get a map from a disc to a half plane or a half sphere though. Dmcq (talk) 19:12, 22 November 2016 (UTC)
Descartes vs. Ptolemy
I just read a blurb about Ptolemy's system of latitude and longitude. I had always assumed that this was an adaptation of Cartesian coordinates to the surface of the Earth, but Descartes was 17th century and Ptolemy's work was known in Europe in the 15th century. As it stands it seems like Descartes' system of coordinates is just a trivial adaptation of Ptolemy, so what am I missing/misunderstanding here? --RDBury (talk) 23:51, 20 November 2016 (UTC)
- Analytic geometry has some history of the concept. Convenience link for others: Geography (Ptolemy).
- Descartes was not the first to use numerical coordinates to describe geometrical positions, and probably neither was Ptolemy (after all, "50 stadia after Rome on the road to Napoli" is a coordinate of some sort). The conceptual step in analytic geometry is that those coordinates are used in calculations, for instance to find the location of the intersection of two straight lines, so that one can make conclusions about the geometry by the means of arithmetic. TigraanClick here to contact me 11:42, 21 November 2016 (UTC)
- Thanks. So it was the method rather than the actual coordinate system. Several times I've heard the story that Descartes invented the system while watching a fly on the wall. One has to wonder how much truth there is in it since there so many cases where such things are copied from source so source, but when you try to trace it back to a contemporary account it's nowhere to be found. Perhaps the fly was actually on a map. --RDBury (talk) 17:59, 21 November 2016 (UTC)
November 21
Cycloid arc length
Can someone take a look at this page here and tell me how does it prove in this sketch that on the cycloid? It doesn't make much sence to me even for a non-rigorous proof. יהודה שמחה ולדמן (talk) 01:16, 21 November 2016 (UTC)
- "I don't understand" is not a question that a reference desk is suited to answer. The relevant discussion is on page 8 of that document. (You could have saved me, and anyone else trying to help, 2 minutes by pointing this out yourself.) What precisely don't you understand from that argument? --JBL (talk) 20:32, 22 November 2016 (UTC)
History of computer science discipline
Please answer on the Computing Reference Desk |
---|
The following discussion has been closed. Please do not modify it. |
Hi all,
|
Meaning of "algebraically increased by an amount equal to"
What does this mean (PDF file):
- (a) When p is 101 325 Pa and t is one of the temperatures listed in the attached table then the magnitude of the density in kg.m^-3 is as stated in the table, which is derived from the following formula:
- d_t = 13 595.08 / {1 + (18 150.36 t + 0.702 09 t^2 + 2.865 5 × 10^-3 t^3 + 2.621 × 10^-6 t^4 ) × 10^-8 }
- where d_t is the density in kg.m^-3 , and t is the temperature in °C;
- (c) When p differs from 101 325 Pa the magnitude of the density in kg.m^-3 as stated in the attached table or derived therefrom in accordance with the above linear interpolation shall be algebraically increased by an amount equal to 5.47 × 10^-7 (p - 101 325);
Do you multiply d_t by "5.47 × 10^-7 (p - 101 325)", divide by it, or what? 166.186.168.191 (talk) 02:55, 21 November 2016 (UTC)
- I understand this to mean that you calculate d_t from the table (or directly from the formula if you wish) and then add (or subtract) a correction equal to 5.47 x 10^-7 kg/m^3 times the amount that the pressure is above (or below) 101,325 Pa. So for a pressure of 101,326 Pa you would add a correction of 5.47 x 10^-7 kg/m^3. For a pressure of 101,323 Pa you would subtract a correction of 10.94 x 10^-7 kg/m^3 etc. The correction appears to be a function of pressure only, and not of temperature. Gandalf61 (talk) 11:06, 21 November 2016 (UTC)
November 25
Polynomial coefficients generated by a sum of powers
Is there a general algorithm to generate the coefficients of the expansion of ? For example, . I could use polynomial interpolation on the first terms of the series, but that gets impractical quickly if is large. 24.255.17.182 (talk) 21:47, 25 November 2016 (UTC)
- One interesting thing I noticed is that is invariant with respect to , and starts out , but I don't see an obvious pattern here and this series isn't in OEIS. 24.255.17.182 (talk) 22:13, 25 November 2016 (UTC)
- (ec) Express the powers as linear combinations of binomial coefficients and use the Hockey-stick identity.
- Bo Jacoby (talk) 22:24, 25 November 2016 (UTC).