Wikipedia:Reference desk/Archives/Mathematics/2009 December 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 16

Multiply Intrinsically 4-Palindromic Numbers

Resolved

If anyone can come up with a theoretical reason there would be no numbers that can be written in the form abba in four different base systems, it would explain why the program I wrote pumped out 9, 624 and 19040 immediately and has not given another peep in two hours.Julzes (talk) 04:40, 16 December 2009 (UTC)

I guess I shouldn't leave the helpers to guess that the program is designed to find the first numbers that can be written in n different ways as abba with n increasing in steps of 1. 624=4444₅ and 1551₇, and I have not checked what 19040 is.Julzes (talk) 04:57, 16 December 2009 (UTC)

I think this is a case where the best place to start is with heuristic probabilities. I haven't worked out all the details myself, but this may get you started. We know that in order for n to have four digits base x, x must be between the 5th and 4th root of n. Heuristically, we may assume that the probability of n being a palindrome base x in this case is 1/x². So the expected number of times that n is a palindrome is approximately

$\int _{n^{\frac {1}{5}}}^{n^{\frac {1}{4}}}{\frac {1}{x^{2}}}dx=n^{-{\frac {1}{5}}}-n^{-{\frac {1}{4}}}$

which tends to 0, but slowly. The next step is to work out the probabilities that a given n is a palindrome in exactly 1 way, 2 ways, etc. Heuristically (again), we can assume this is Poisson distribution with λ equal to the expected value above. We're only interested in asymptotic values here so we can simplify things by putting λ = n^-1/5 and e^-λ = 1, so the probability that n is a palindrome in 4 ways is approximately kn^-4/5 for some k. Finally, integrate this from 1 to m to get the expected number of integers less than m that can be written as a palindrome in 4 ways is approximately km^1/5. This goes to infinity but slowly and if k is small it will require a large m, and m must be assumed large to make the asymptotic analysis valid; possibly m must be larger than the allowed size of integers in your computer language before you get an expected value of 1. Keep in mind that none of these heuristic arguments hold up in court; there's no such thing as a theorem being probably true. Plus these are just ball park calculations and should be checked. But it sometimes makes sense to do this kind of analysis when the problem is intractable otherwise, and I'm pretty sure that's the case here.--RDBury (talk) 06:42, 16 December 2009 (UTC)

Well, there isn't the theoretical reason I thought someone might know, and the problem isn't intractable in the fourth term. It's just quite a lot larger than the third: 30222192. Thanks for the thoughts on scale approximation. I use PARI/GP on a recent model computer, so I think I might expect a fifth term at some later date, though perhaps I might want to write a better program.Julzes (talk) 06:57, 16 December 2009 (UTC)

When I said intractable I meant to solve it theoretically rather than by brute force. Running a program on a problem like this might give you a solution, or it might not, but it can't tell you for example if there are an infinite number or whether you can expect one if you let the program run long enough.--RDBury (talk) 07:34, 16 December 2009 (UTC)

I missed your meaning. Yeah, I don't think there would be any analytical way to solve it, though perhaps there is a proof out there that the sequences beginning with 4-palindromes are finite. It's easy to prove that the 2-palindrome case gives an infinite sequence, and I would guess that proof of an infinite sequence for 3-palindromes is not too difficult--might even be at hand.Julzes (talk) 07:47, 16 December 2009 (UTC)

Incidentally, the n-fold intrinsically 3-palindromic numbers keep on coming, I got a third but not fourth term for the 5-palindromic case so far, and the first doubly 6-palindromic number has 10 as one of the bases (207702) just like the very first 6-palindromic number. I'm not being as thoroughly systematic as I might be. I'm just pumping out quick results that I don't really understand. The 2-palindromes are relatively simple, with a formula I have to work out.Julzes (talk) 07:13, 16 December 2009 (UTC)

Submissions on this to OEIS are in progress, though I may just submit three terms for 5-palindromes and stop there in the worst case scenario.Julzes (talk) 07:50, 16 December 2009 (UTC)

For the 2-palindrome case, if anybody has a good closed way (simple or not) of writing the following as a formula, it will be credited as part of the comments: The first n-fold intrinsically 2-palindromic number is the smallest number k such that 1) if k is a square, (d(k)-1)/2=n; 2) if k is of the form m^2+m, (d(k)-2)/2=n; and 3) otherwise, d(k)/2=n.Julzes (talk) 08:05, 16 December 2009 (UTC)

I shut down the 4-palindrome case for now in order to report on the 7-palindrome case (cpu was at 100%). This is fantastic, so hold your hats: The first 3-fold intrinsically 7-palindromic number is 6281826₉=3360633=1995991₁₁! I still don't have a 3-fold 6-palindrome.Julzes (talk) 09:24, 16 December 2009 (UTC)

I may be missing something in this discussion. What have you with four different bases? Your 624 is palindromic in bases 5 (4444), 7 (1551) and 12 (0440) which is three bases. Also are you constraining your palindromes to 4 digits? 19040 is palindromic in base 13 (8888), 15 (5995), 19 (2EE2), 34 (0GG0) which is four bases. (BTW, in base 17 19040 looks a bit like pi: 3.14.15.0) -- SGBailey (talk) 09:26, 16 December 2009 (UTC)

You are welcome to tell me in what 4 bases 30222192 is 4-palindromic, 0 is not an allowable leading digit according to OEIS and common sense, and the pi comment I could do without. The 3-palindromic case, like the relatively trivial 2-palindromes, was good for an ever larger number of simultaneous bases. I shut that down around 22 or 23.Julzes (talk) 14:49, 16 December 2009 (UTC)

Also, (trivially) any number p (>2) is also palindromic in base-p (=010_p) and base-p-1 (=11_p-1). So 19040 is palindromic in (at least) 6 bases. (Speaking of trivial cases, p is palindromic in all bases ≥(p-1) ) Abecedare (talk) 09:44, 16 December 2009 (UTC)

I don't know if this observation helps: In any base abba = 11 * (101a + 10(b - a)). If the bases are n₁, n₂, n₃, n₄ then it must have factors (n₁ + 1), (n₂ + 1), (n₃ + 1), (n₄ + 1). I don't think this proves anything on its own, but it could speed a search: you need only check a base n if (n+1) is a factor. JohnBlackburne (talk) 10:27, 16 December 2009 (UTC)

More generally for any even palindrome "11", i.e. (n +1) where n is the base, is a factor. E.g. abccba == 11 * (a * 10101 + (b - a) * 1010 + (c - b) * 100), where each of 11, 10101,1010, 10 is understood to be a number in the base being considered. --JohnBlackburne (talk) 12:33, 16 December 2009 (UTC)

Also if base 1 (1^0, 1^1, 1^2, 1^3,...) is the relevant number of 1s (I count 1,11,111,1111,11111 then all positive integers are palindromic! What about base phi? -- SGBailey (talk) 14:09, 16 December 2009 (UTC)

Leading digit 0 is not part of the standard problem that OEIS sequences already in existence address. If someone wants to research variants, leading digit being 0 and the problem equivalent to allowing digits greater than or equal to the base are open, I'm sure. I haven't looked at base phi, though aware of its existence and vaguely conscious of how it functions. Someone who wants to investigate and claim credit for listing its palindromes may go right ahead without my pre-emption. I just started and will soon stop this line of inquiry. They just seemed like obvious simple and mildly interesting questions that I could do something with/about. The start of the inquiry here was under the presumption that someone might be able to place the 4-fold 4-palindromes as impossible on some deep theoretical grounds.Julzes (talk) 14:49, 16 December 2009 (UTC)

I think most people regard base 1 as not being a positional base system, but more like a tally. Being trivial, it's not at all considered here. I'm going to mark this resolved now, but look back if you are interested in either what bases 30222192 is 4-palindromic in or what the first triply 6-palindromic or doubly 8-palindromic numbers are (I'll calculate the first thing now; and if I get the latter two any time soon, I'll post them.)Julzes (talk) 16:40, 16 December 2009 (UTC)

The bases are 87, 110, 135 and 271, and I'll leave unsaid what the actual digit values are unless someone else wants to post them (I'm lazy, so the program to get the bases didn't generate the digits and I don't feel like calculating them). The other things people have been told to wait for if they are interested will be sought only after I've written a better general program, but sooner than would have been the case probably if I weren't going to write it.Julzes (talk) 18:30, 16 December 2009 (UTC)

A word to the wise about careful programming: I ran a new version on the 4-palindrome case that pumped out the number about whose existence I was initially wondering in half a minute. It hasn't pumped out a fifth term since I started this post, but it looks like even a sixth is apt to be found (though I'm just guessing until I either get that far or give up).Julzes (talk) 23:41, 16 December 2009 (UTC)

Before I put my cpu well into the red for a while, I may as well report a couple of more results: 1) The first 5-fold 4-palindrome is 592704000 in base ten, and 2) The first 4-fold 5-palindrome is 4838419019 in base ten.Julzes (talk) 03:49, 17 December 2009 (UTC)

Well, I'm back. Got a 2-fold 8-palindrome immediately: 342324801 in base ten is a palindrome in base 12 and some higher base. Now I'm going to start running the 9-palindrome version, and can't come back for a while.Julzes (talk) 04:12, 17 December 2009 (UTC)

I was going to have a crash with or without the internet. I shut down the 7-digit case to keep other things going, and I have that first 3-fold 6-palindrome finally: 2853326516320 in base ten is 6-palindromic for three different bases starting with base 139.Julzes (talk) 14:13, 17 December 2009 (UTC)

This just in (my head). It's elementary to get a number which is, for a fixed n, an n-palindrome an arbitrarily large number of ways. All one needs is to have there be no carries in the expansion of N=[m*(B+1)]^(n-1) for a large enough number of pairings of factors. I'll leave that in more detail to the reader, if there is one. Anyway, I submitted what I had of all of the sequences from 2-palindromes to 7-palindromes, and the sequences for 2-fold, 3-fold and 4-fold with increasing lengths. They have all been accepted. I found something else nice to mention on the topic. The first number which is a palindrome of all lengths up to 6 is surprisingly small: 1885 in base ten. The numbers for up to 5 and up to 4 are 130 and 52, and 5 and 3 are trivial starting terms of a sequence I also submitted. Search for another term is ongoing, but not wholeheartedly expected to generate a result before I give up. No other data has come in on the other sequences--no 2-fold 9-palindrome, for instance.Julzes (talk) 01:05, 19 December 2009 (UTC)

Given how this question started, the finding of a 6-fold 4-palindrome, 12040481088, shows how off-base I was.Julzes (talk) 10:28, 19 December 2009 (UTC)

The first number which is a palindrome of all lengths through 7 is 2^30, with bases 31,63,127, and multiple bases for the shorter lengths. Little hope of extending this sequence.Julzes (talk) 21:44, 19 December 2009 (UTC)

I still don't have the smallest doubly 9-palindromic number or anything else new. On the other hand, I expect to have the result that the first number which is a palindrome of all lengths through 8 digits is 2^42 by tomorrow,overthrowing the expectation of the last post. Also, I had a little bit of a worry that I might have in some cases only generated the numbers that are multiply palindromic (of certain lengths) with the smallest first base in which they are palindromic, but every number generated turned out to be correct after some checking.Julzes (talk) 18:17, 21 December 2009 (UTC)

I just discovered something that has to be one of the biggest base-ten coincidences, and it just barely escaped prior discovery, it seems. The number 3360633 turns up in palindrome lists for two different reasons. The second-discovered one is that mentioned above that it is the smallest number that is 7-palindromic in three bases. The current OEIS sequence that covers numbers that are palindromes in bases 9 an 10 comes up short, just barely. The other way 3360633 comes up is as the 8th member of a sequence someone dreamed of researching that is a little unusual: Sums of all composites up to some value that are palindromes in base ten. The 6th member of that sequence is 33633.Julzes (talk) 08:38, 22 December 2009 (UTC)

2^42=4398046511104 is indeed the smallest number that is a palindrome of all lengths through 8 digits.Julzes (talk) 21:41, 22 December 2009 (UTC)

Finite differences of factorials

In finite differences we have delta(u/v)=(1/v)delta(u)-(u/v2)delta(v).

For factorials, this should mean delta((n+j)!/n!=[(1/n!)((n+j+1)!-(n+j)!)]-[((n+j)!/(n!)^2))((n+1)!-n!)], where the delta for (n+j)! and n! have been taken from previous posts.

This seems to lead to [(n+j+1)!/n!)-(n+j)!/n!)]-[((n+j)!/(n!)^2)*(n+1)!-((n+j)!/n!],

which, after cancellation of terms, gives [(n+j+1)!/n!)]-[((n+j)!/(n!)^2)*(n+1)!].

A little algebraic manipulation then yields (n+j+1)(n+j)!/n!-(n+1)(n+j)!/n!,

which finally simplifies to j(n+j)!/n!.

But is this the correct answer?

From one point of view the answer looks good - when j is zero so is the finite difference, which is as it should be, because then we are taking the finite difference of a constant (n!/n!).

Apologies for my lack of knowledge of finite differences but I never took any courses in them, only in differentiation and integration (and of course factorials cannot be differentiated, and the gamma function is not unique in the sense that it is only one of several extensions of factorials to the real numbers). Also, I have looked up finite differences of factorials in Wikipedia but have not found anything dealing with the subject - unless it has been added very recently, say, in the past week. If Wikipedia is supposed to be a learning experience, well, I have been learning from the answers to my questions. Thanks to everyone.ImJustAsking (talk) 12:14, 16 December 2009 (UTC)

The denominator seems to be wrong (check j=1). In fact

${\frac {(n+j+1)!}{(n+1)!}}-{\frac {(n+j)!}{n!}}={\frac {(n+j+1)!-(n+1)(n+j)!}{(n+1)!}}=$${\frac {[(n+j+1)-(n+1)](n+j)!}{(n+1)!}}=j{\frac {(n+j)!}{(n+1)!}}.$--pma (talk) 17:29, 16 December 2009 (UTC)

Which means that the delta is "j(n+j)!/(n+1)!" [with (n+1)! instead of n! in the denominator]. It seems unusual how in the end that "+1" gets in the denominator and not also in the numerator, but there is no arguing with your math - it works. Thanks for the correction. —Preceding unsigned comment added by ImJustAsking (talk • contribs) 19:00, 16 December 2009 (UTC)

combinatorics (pigenhole etc)

Resolved

I am having trouble proving the following result given in my book.

Let $r\geq 2$. Show that there exists a least positive integer M=M(k;r) so that any r-coloring of M integers admits a monochromatic monotonic k-term subsequence. Determine M(k;r).

My attempt is as follows: Use induction on r. For r=1 the result holds good because every $(k-1)^{2}+1$ term sequence has a monotonic k term subsequence, by a result already established in the book, using the pigeonhole principle. Suppose the result holds for r-1. Let n=M(2k+1;r-1). Consider any sequence $a_{i}$ of n elements. Go color blind and assume r-1 and r is the same color. Now if we have a monochromatic monotonic subsequence of the first r-2 colors we are done, else regain sight to end up with a 2k+1 term monotonic subsequence. By the pigeonhole principle it will have a k-term monochromatic monotonic subsequence thereby finishing the problem.

My questions are as follows:

• Is the above proof correct?
• Is there a simpler way?
• My proof only establishes that M(k;r) ≤ M(2k+1;r-1). The problem specifically asks us to determine M(k;r). How can I do that?

Thanks and regards. -Shahab (talk) 13:06, 16 December 2009 (UTC)

I'd start by considering the r colors separately. By the earlier result, we can arrange at most (k−1)² integers of each color such that there is no monotonic k-term subsequence of that color. Thus, the maximum number of integers we can r-color without a monotonic monochromatic k-term subsequence is r (k−1)², and thus M(k;r) = r (k−1)² + 1. —Ilmari Karonen (talk) 15:12, 16 December 2009 (UTC)

This may be a stupid question but I don't understand how you reach the conclusion that the max number of integers we can r-color without a monotonic monochromatic k-term subsequence is r (k−1)². I understand that we can arrange at most (k−1)² integers of each color such that there is no monotonic k-term subsequence of that color. Why does this guarantee that the maximum when all colors are used (not combined, but used) r (k−1)²? I feel there is a logical flaw somewhere which I can't put my finger on. Perhaps you would be kind enough to clear my doubt.-Shahab (talk) 15:23, 16 December 2009 (UTC)

Choose a sequence of integers and fix a given r-coloring on it. Then the sequence obviously^[1] has no monochromatic monotonic k-term subsequence if, and only if, it has no monotonic k-term subsequence of color c for any color 1 ≤ c ≤ r. This can only be true if there are at most (k−1)² terms of each color, which in turn can only be true (per the pigeonhole principle) if the entire sequence has at most r (k−1)² terms total. Thus, an r-colored sequence with r (k−1)² + 1 terms must have a monochromatic monotonic k-term subsequence, showing that M(k;r) ≤ r (k−1)² + 1.

Conversely, we can clearly construct an r-colored sequence of r (k−1)² integers which indeed has no monochromatic monotonic k-term subsequence; we may do so by, say, taking r copies of a (k−1)²-term sequence with no monotonic k-term subsequence, concatenating them and coloring each of the copies a different color. In any case, it does not matter how we construct the sequence, merely that it can be constructed and thus exists, thereby showing that M(k;r) > r (k−1)². —Ilmari Karonen (talk) 19:58, 16 December 2009 (UTC)

^[1] This bit should be obvious; it it's not, one of us has misunderstood something. —Ilmari Karonen (talk) 20:03, 16 December 2009 (UTC)

Thanks. Its all clear now.-Shahab (talk) 04:31, 17 December 2009 (UTC)

Distributivity

I am trying to understand what distributivity actually means and so far have not come across anything useful. I originally thought that it meant that the order of two operations is inconsequential and that, in the example x*(y+z), performing addition then multiplication or vice versa achieves the same result but I was told this was wrong. Can anyone enlighten me? Thanks 92.0.129.48 (talk) 20:36, 16 December 2009 (UTC)

Distributivity (in the context of addition and multiplication of real/complex numbers) means simply: x*(y+z)=xy+xz. That is all there is to it. In other situations, you also need to specify that (x+y)*z=xz+yz, but multiplication of real or complex numbers is commutative (xy=yx), so the two are equivalent. --Tango (talk) 20:43, 16 December 2009 (UTC)

Also, we do have an article on distributivity. It basically starts at the definition Tango gave above and goes into further detail. —Ilmari Karonen (talk) 09:57, 17 December 2009 (UTC)

double-checking statistics

I always screw up statistics, so I'm double-checking... Given n. I will generate n random numbers between 1 and n inclusive. The probability that there will be at least one repeat number is (n-1)!/n, correct? Is there an easy way to calculate the statistics for the number of repeats and standard deviation? I know that I could just write a program to simulate it a few millions times for each n, but I want to write a statistical proof. -- kainaw™ 21:51, 16 December 2009 (UTC)

What? $n>3\rightarrow {\frac {(n-1)!}{n}}>1$. --Tardis (talk) 22:10, 16 December 2009 (UTC)

Let me be a bit more helpful: the probability of a repeat is exactly $1-{\frac {n!}{n^{n}}}$. As far as counting repeats, do you mean $|\{y:\exists i\neq j\;x_{i}=x_{j}=y\}|$ or $|\{i:\exists j\neq i\;x_{i}=x_{j}\}|$ or what? --Tardis (talk) 22:15, 16 December 2009 (UTC)

I realize that I left the power of n off the denominator. I assumed it was (n-1)!/nⁿ. By repeat, I mean the second. What is the average number of elements (regardless of value) that are a repeat? -- kainaw™ 22:31, 16 December 2009 (UTC)

As Tardis notes, the probability of at least one repeat is 1−n!/nⁿ; this can be easily derived by noting that there are nⁿ possible mappings from an n-element set to itself, of which exactly n! are permutations. The probability of a randomly chosen mapping being a permutation (and thus having no repeats) is therefore n!/nⁿ.

As for the expected number of repeats, I don't have an exact formula. However, if n is large enough, it should be possible to approximate the number of times each of the n values occurs as n independent Poisson-distributed random variables with mean 1. Under this approximation, the probability of a given value occurring exactly once is the same as the probability of it never occurring: 1/e. Thus, the expected number of values that occur more than once (Tardis's first definition) is n(1−2/e), and the expected number of occurrences of those values (Tardis's second definition) is n(1−1/e).

(As a consistency check, this approximation predicts the probability of the being no repeats to be about 1/eⁿ for large n. This value tends to zero as n tends to infinity, but its n-th root is constant 1/e. A quick check with Maple shows that, indeed, (n!/nⁿ)^1/n tends to 1/e as n tends to infinity. I'm sure showing this without computer assistance would be much more illuminating, but I was lazy and couldn't think of a good way to do it by hand just now.) —Ilmari Karonen (talk) 10:43, 17 December 2009 (UTC)

Thanks. I am working with n in the range of around 100,000. So, I pretty much get a guarantee of a repeat - which I understand. However, it appears that by increasing the size of n, the number of times a single element will repeat is very small - which is good. I don't mind seeing an element 2 or 3 times now and then, but I don't want to see the same element 100 times. Further, this is all based on short-circuiting the loop before I sample n times from a population of n elements. If I stop after sampling 10% of the population, my probability of a repeat decreases and the number of repeats decreases. So, statistically, I can claim that I've pretty much sampled 10% of the population, not something like 5% of the population twice each. -- kainaw™ 15:09, 17 December 2009 (UTC)

If you take rn samples from a population of n, then under the same Poisson approximation as above the expected number of distinct members sampled is approximately n(1−1/e^r). For small r this is approximately rn, as one would expect. —Ilmari Karonen (talk) 22:29, 17 December 2009 (UTC)

That $\lim _{n\rightarrow \infty }{\frac {n!^{1/n}}{n}}={\frac {1}{e}}$ follows immediately from Stirling's approximation. --Tardis (talk) 18:18, 17 December 2009 (UTC)

items arranged question

Ok, this might be a little complicated, but here goes.

If you have ever played the game mastermind, it is kind of like that.

I have 12 (non-repeating) objects arranged in a certain order.

Lets just say like this

1. A

2. B

3. C

4. D

5. E

6. F

7. G

8. H

9. I

10. J

11. K

12. L

And someone else, knowing what the objects are, but not the order, arrange the items, and I tell them which are in the correct position. How many times would they need to submit a guessed arrangement before they end up with the correct one? (Call it a 75% or higher rate of success) Googlemeister (talk) 22:24, 16 December 2009 (UTC)

As a start, look at the rencontres numbers: with no information, they govern the probability distribution over the number of objects guessed correctly. As the game progresses, they become less useful: the player who first tries the ordering BCDEFGHIJKLA and gets nothing right now knows more than they did when they started, so (with intelligent play) will do better than chance on the second try.

After r rounds, suppose the player has k out of your n=12 items placed correctly. Ideally the player would then have tried in each other slot r out of the n-k other possibilities already, and have only n-k-r possibilities left for each remaining slot. But if (as is extremely likely) some of the correctly-placed items were tried in a slot whose value is still unknown, there remain more possibilities for that slot. The true answer will lie somewhere between the optimistic answer and the probabilities in the article. --Tardis (talk) 22:45, 16 December 2009 (UTC)

It will take 12 guesses maximum. Consider this one item at a time. For A, there are 12 possibilities for where it belongs. At most, 12 attempts to place A will be made. For B, the same applies. For C, the same applies. For each item, the same applies. After 12 attempts to place each item, each item will be placed. The actual number of guesses will be less than 12 because items will be placed. For example, if 1 item is placed correctly on the first guess, no other item will be placed there, so each item will only require 11 guesses maximum. Calculating the statistical mean is a bit more difficult. In the first attempt, there is a 1/12 chance that any of the 12 items will be placed correctly. How many are placed correctly will alter the probability of the remaining items. How many are placed correctly in the second guess will alter the probabilities for the third guess and so on. -- kainaw™ 02:48, 18 December 2009 (UTC)

You're right that 12 guesses are sufficient; you can just rotate every item through every slot and stop each one when it sticks. I don't know if this is the optimum strategy, but that strategy can take all 12 guesses in the case that I suggested first (where everything is off by one) if you are unlucky and rotate the wrong way. The number of guesses that get nothing right is the number of derangements: for 12 items the probability is 36.8% — so you have almost a 2/3 chance of getting something right on the first try. --Tardis (talk) 05:18, 18 December 2009 (UTC)