- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] RE: True So Far
by Lior Manor 25 Feb '05

25 Feb '05

Yes, I had a problem with the indices, it's 2024. I just saw your comments in the OEIS and I got the same numbers. ________________________________ From: PlasteredDragon(a)comcast.net [mailto:PlasteredDragon@comcast.net] Sent: Thu 24-Feb-05 23:28 To: Lior Manor; Eric Angelini Cc: math-fun Subject: RE: True So Far Hi Lior, Your list of last terms looks good to me, but I'm curious about your indices. By my count True So Far (in base 10 anyway) only has 2024 terms in it. -- Chuck -------------- Original message -------------- > Hi Eric, > > Looks like a(6078) = 8945 is the last term of your sequence. > According to my calculations the last terms ending with 0-9 digits are: > a(5914) = 5890 > a(6060) = 8201 > a(6064) = 8302 > a(6073) = 8613 > a(6075) = 8734 > a(6078) = 8945 > a(6059) = 7756 > a(6067) = 8563 > a(6051) = 6778 > a(5918) = 5979 > It is easy to see that there will be no additional terms. > You can view the full sequence in sci.misc > (http://groups-beta.google.com/group/sci.misc/msg/aa57ea84b421d2a2) > > Lior Manor > >

1 0

[math-fun] Zeroless powers of 2 and Wilson's conjecture.
by David Wilson 24 Feb '05

24 Feb '05

Since the discussion has again rolled around to the perennial chestnut of whether there are a finite number of zeroless powers of 2, I thought I would again state my perennial umbrella conjecture. To start, if we are given two arbitrary integer sequences each exhibiting exponential growth, a probabilistic argument says that we should expect the sequences to share only a finite number of elements. There are cases where we can prove the number of shared elements is finite (e.g, {2^n} and {3^n}) and others where we know the number of shared elements is infinite (e.g, {Fib(n)} and {Fib(2n)}), but in the absence of evidence either way, the safer assumption is a finite intersection. A b-automatic (b >= 2) set is a set of nonnegative integers whose base-b representations form a regular language, that is, are accepted by a finite automaton and representable by a regular expression. For example, the powers of 2 form a 2-automatic set with the regular expression 10*. Similarly, the zeroless numbers form a 10-automatic set with regular expression (1+2+3+4+5+6+7+8+9)(1+2+3+4+5+6+7+8+9)*. Call two bases b and c compatible if b and c share a common power > 1. Thus binary, octal and hexadecimal are compatible bases because 2, 8 and 16 have the common power 4096. If b and c are compatible, then the b-automatic and c-automatic sets coincide. If b and c are incompatible, the sets that are both b-automatic and c-automatic sets include precisely the finite sets and sets whose first differences are eventually periodic (Cobham 1964). ---------------------------------------------------------- Let B be a b-automatic set with density 0 over the integers. It can be proved that B is either finite or exhibits exponential growth (as a sorted sequence). Let B be a zero-density b-automatic set and C a zero-density c-automatic set. If b and c are compatible, it is easy enough to find B and C having either finite or infinite intersection. For finite intersection, let B = C = S = {1,2,3} (or any other finite set). By virtue of its finiteness, B = C = S is both b-automatic and c-automatic, as well as zero-density, and the intersection of B and C is S, which is finite. For infinite intersection, let B = C = S = {b^n}. B = C = S is zero-density over the positive integers. B is b-automatic, having base-b regular expression 10*. Because c is compatible with b, C = B is also c-automatic. The intersection of B and C is S, which is infinite. If b and c are incompatible, it is easy enough to find B and C with finite intersection. For example, b = 2 and c = 3 are incompatible. Let B = {2^n} and C = {3^n}. B and C are 2-automatic and 3-automatic respectively, having regular expression 10* in their respective bases, and their intersection is {1}, which is finite. On the other hand, I have not been able to find such a B and C with infinite intersection, which leads to the conjecture: Wilson's Conjecture: If b and c are incompatible bases, then zero-density b-automatic set B and zero-density c-automatic set C have finite intersection. (I adopt this conjecture because I have not seen it elsewhere). Since B and C are zero-density automatic sets, they are either finite or exhibit exponential growth. If either is finite, their intersection is cleary so. If both have exponential growth, applying our statistical argument above, we would expect them to have finite intersection. So what Wilson's conjecture really says is that the incompatibility of bases b and c can be taken as evidence that B and C are "relatively random" enough to obey the probabilistic argument that indicate finite intersection. ---------------------------------------------------------- Admittedly, Wilson's conjecture is a yet another generalization of certain problems that are themselves notoriously difficult to prove. However, I think that it is a useful generalization in that (1) it tells us what to expect in a large number of similar problems, and (2) it has number theoretical implications beyond mere digit twiddling. The finity of the zeroless powers of 2 is a straightforward consequence of Wilson's conjecture. The generalization is easy enough to show: Let b and c be incompatible bases, and let d be a base-c digit (0 <= d < c). The powers of b form a zero-density b-automatic set B, while the base-c numbers without digit d form a zero-density c-automatic set C. Wilson's conjecture then implies the intersection of B and C is finite, that is, there are finitely many base-c powers of b witout digit d. Letting b = 2 and c = 10 are incompatible, and we get a finite number of zeroless base-10 powers of 2. If instead of powers of 2, we had chosen a sequence S to be a random sequence of base-10 numbers such that S(n) has the same number of digits as 2^n, S would have had a finite number of zeroless elements with probability 1. So in this case, Wilson's conjecture tells us that in one respect the powers of 2 act like similarly sized random numbers with respect to base 10. More generally, Wilson's theorem says something about the "relative randomness" of incompatible bases in certain contexts. Anyone who has programmed arbitrary precision arithmetic knows that converting between compatible bases is computationally easy while converting between incompatible bases is difficult. To convert between compatible octal and hexadecimal bases, one can simply start at the right, converting each block of 4 octal digits to an equivalent block of 3 hexadecimal digits, and O(n) process. Converting between incompatible binary and decimal is much harder. Changing a single base-2 digit potentially affects arbitrarily many base-10 digits. I'm not even sure that a sub-O(n^2) algorithm exists for binary-to-decimal conversion. This is one aspect of the "relative randomness" of incompatible bases. I am taxed to remember the details of a certain prize problem concerning the divisibility of choice numbers by 4 and 9 (any help finding this problem would be appreciated). The problem asked whether there were a finite number of choice numbers with a certain property, and the conjectured solution was implied by Wilson's theorem. So here was an instance of an independent number theoretical (as opposed to digit twiddling) problem where Wilson's theorem gave the expected result. Another purely number theoretical implication of Wilson's theorem is that for incompatible b and c, |b^x - c^y| <= d has a finite number of solutions. This result, whether true or false, probably has a goodly amount of number theoretical background, which might be reversed engineered to shed light on Wilson's theorem. -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.300 / Virus Database: 266.4.0 - Release Date: 2/22/2005

1 1

Re: [math-fun] Bob Dylan
by Paul Reiners 24 Feb '05

24 Feb '05

Like Schillinger, Copland, and Stravinsky, Bob has alway been a math/music hacker: http://www.therestisnoise.com/2004/10/bob.html On 2/24/05 2:53 PM, "Marc LeBrun" <mlb(a)fxpt.com> wrote: > "I wouldn't even think about playing music if I was born in these times... > I'd probably turn to something like mathematics. That would interest me." > --Bob Dylan > > > (Either that, or maybe a Victoria's Secret spokesmodel?)

1 0

[math-fun] RE: True So Far
by PlasteredDragon＠comcast.net 24 Feb '05

24 Feb '05

Hi Lior, Your list of last terms looks good to me, but I'm curious about your indices. By my count True So Far (in base 10 anyway) only has 2024 terms in it. -- Chuck -------------- Original message -------------- > Hi Eric, > > Looks like a(6078) = 8945 is the last term of your sequence. > According to my calculations the last terms ending with 0-9 digits are: > a(5914) = 5890 > a(6060) = 8201 > a(6064) = 8302 > a(6073) = 8613 > a(6075) = 8734 > a(6078) = 8945 > a(6059) = 7756 > a(6067) = 8563 > a(6051) = 6778 > a(5918) = 5979 > It is easy to see that there will be no additional terms. > You can view the full sequence in sci.misc > (http://groups-beta.google.com/group/sci.misc/msg/aa57ea84b421d2a2) > > Lior Manor > >

1 0

[math-fun] Bob Dylan
by Marc LeBrun 24 Feb '05

24 Feb '05

"I wouldn't even think about playing music if I was born in these times... I'd probably turn to something like mathematics. That would interest me." --Bob Dylan (Either that, or maybe a Victoria's Secret spokesmodel?)

1 0

[math-fun] RE: True So Far
by Lior Manor 24 Feb '05

24 Feb '05

Hi Eric, Looks like a(6078) = 8945 is the last term of your sequence. According to my calculations the last terms ending with 0-9 digits are: a(5914) = 5890 a(6060) = 8201 a(6064) = 8302 a(6073) = 8613 a(6075) = 8734 a(6078) = 8945 a(6059) = 7756 a(6067) = 8563 a(6051) = 6778 a(5918) = 5979 It is easy to see that there will be no additional terms. You can view the full sequence in sci.misc (http://groups-beta.google.com/group/sci.misc/msg/aa57ea84b421d2a2) Lior Manor

1 0

[math-fun] not proven: 2^86
by Richard Schroeppel 24 Feb '05

24 Feb '05

Rich>My favorite effort in this direction is "2^86 is the last power of 2 >without a 0 digit". David Gale> Really? In my Automatic Ant book (page 43) I speculate that statements like "there are only a finite number of 7-less powers of 2" may be undecidable, in the Godel sense that there exists no proof of the statement nor of its negation from the standard axioms. Rich, you apparently have a proof with 7 replaced by 0. Could you elaborate? Whoa! Nellie! I have NOT proved 2^86 is the last power of 2 with no 0. It's a CONJECTURE. All the proof I have will fit comfortably in an arbitrarily small margin. I should have been more careful in my wording. My apologies for the confusion. The only evidence I know of is reported in Hakmem item 57. Mike Beeler wrote a program that checked a block of low-order digits, and we ran it out to exponent 30M. Every power after 2^86 had at least one 0 digit. ---- Here are some notes I made up for power-digit puzzles. The power-matching problem seems more interesting if we allow anagrams. Examples: 125/512, 169/196/961, 256/625, 1024/2401, 4096/9604, 1048576/5764801. Of course 169/961 is a cheat. And I need a rule for handling leading 0s. Here's a "stats-gone-wrong" example: Based on statistics alone, modelling numbers as random digit strings of a known size, 22nd and higher powers should all eventually have a 0 digit, since log10(10/9) = 1-.95424 = .04576 > 1/22. However, there's a parametric exception: (1,1)^22 = 1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432 646646, ... ,22,1. (Pascal's Triangle) 1000001^22 = 1000022000231001540007315026334074613170544319770497420646646705432 646646497420319770170544074613026334007315001540000231000022000001 so (10^n+1)^22 is 8-less for n>=6. Of course, (10^n)^22 is also 8-less, and if k^22 is 8-less, so is (10k)^22. This sort of example don't work for 0-less, since 0 is the padding digit. Variations on 10001 include 10002, 20001, 20003, 100379, 23400765, 1001001, 9999, 29993, 299930001, etc. Powers of these could be 8-less in a more or less ad hoc way, and could be extensible. Is there a parametric set of 0-less squares? 777...444 seems to fail. 9999^2 = 99980001. Divide by 9 to get 3333^2 = 11108889. Close, but no cigar. [RIP WAH]. Multiply by 4 to get 6666^2 = 44435556. Bingo. Is there any way to find 0-less powers other than scanning for them? Presumably the 0-less squares thin out but never completely disappear. It might be possible to use stats to prove density upper bounds on 0-less squares or powers of 2. Rich rcs(a)cs.arizona.edu

4 3

RE: [math-fun] test; E. M. Wright; continued fraction convergence; Dyson's problem
by Schroeppel, Richard 23 Feb '05

23 Feb '05

We looked at the cycle of low-order digits of powers of 2 (mod 10^k). 2 is a primitive root of 5, 25, ..., so the cycle lengths are 4, 20, 100, etc. In particular, every even number not ending in 0 actually occurs as a last digit, as does every 2-digit multiple of 4 not ending in 0, and every 3-digit multiple of 8 not ending in 0, and so on. This will let you say (and prove) things like "the tens digit of powers of 2 is a 7, 10% of the time". But this idea doesn't go far enough to prove the 2^86 conjecture. It _can_ show that the density of 0-less powers of 2 is 0. But the density of primes is 0, and there are plenty of them. More interestingly, there's a unique "terminal string" of 1s and 2s for very large powers of 2: it ends with ...2112. No other terminal string (consisting solely of 1s and 2s) occurs for infinitely many powers of 2. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com on behalf of Michael Kleber Sent: Wed 2/23/2005 7:00 PM To: math-fun Subject: Re: [math-fun] test; E. M. Wright; continued fraction convergence; Dyson's problem Rich wrote, > >My favorite effort in this direction is "2^86 is the last power of 2 > >without a 0 digit". David Gale replied: > Really? In my Automatic Ant book (page 43) I speculate that statements like > "there are only a finite number of 7-less powers of 2" may be undecidable, > in the Godel sense that there exists no proof of the statement nor of its > negation from the standard axioms. > > Rich, you apparently have a proof with 7 replaced by 0. Could you elaborate? I'm just guessing, and surely Rich will fill us in soon. But for any k, the last k digits of 2^n are eventually periodic. So if you find a k where every member of the attrating cycle of "n -> 2n mod 10^k" contains a 0, you're done. I'd have to think more about whether we expect such a scheme to succeed or fail in general. As k increases, you have more digits to work with, but also probably more terms in the cycle, and if someone else wants to work out how the probabilities balance against each other, I'm as happy to read it as to do it myself... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen. _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] test; E. M. Wright; continued fraction convergence; Dyson's problem
by David Gale 23 Feb '05

23 Feb '05

> Rich writes, >My favorite effort in this direction is "2^86 is the last power of 2 >without a 0 digit". Really? In my Automatic Ant book (page 43) I speculate that statements like "there are only a finite number of 7-less powers of 2" may be undecidable, in the Godel sense that there exists no proof of the statement nor of its negation from the standard axioms. Rich, you apparently have a proof with 7 replaced by 0. Could you elaborate? David >Rich rcs(a)cs.arizona.edu > > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] test; E. M. Wright; continued fraction convergence; Dyson's problem
by Schroeppel, Richard 23 Feb '05

23 Feb '05

test: If Mime conversion is working, this message should be plain text. ---- E. M. Wright, an author of Hardy & Wright's Introduction to the Theory of Numbers, died recently. ---- My memory of the rule for when CFs converge: If all partial quotients are positive, then the CF values either converge, or oscillate while approaching two limit points. If the sum of the PQs is infinite, then the CF converges. (Is this right? I think the oscillation interval drops roughly by 1/(1+PQ) for each term, and that product ->0 should be same as sum PQ -> infinity.) Of course this leaves open negative and complex partial quotients. ---- I looked at Dyson's problem. (Show that no power of 2 is the reverse of a power of 5, except 1 = 2^0 = 5^0.) There are some easy partial results: Assume a counterexample. Then both are squares and have an odd number of digits, or both are non-squares and have an even number of digits; both are cubes, or both are non-cubes, and of the opposite sense. These come from looking at the powers mod 9 and mod 11. I tried looking at additional moduli like 7, 13, 101, etc. There are restrictions on various digit-position sums, but nothing easy to state. The 1 solution means that solutions exist mod all primes (except 2,5). My favorite effort in this direction is "2^86 is the last power of 2 without a 0 digit". Rich rcs(a)cs.arizona.edu

1 0