[math-fun] Propp/Asimov sequence problem
--NJA Sloane tells me "Dan Asimov's misunderstanding of Propp's question, which of course is https://oeis.org/A165911, ... Does it go into a cycle? WDS gave an inconclusive analysis. The graph of the first 1000 terms (go to the OEIS A165911 entry and click "graph") was also inconclusive. So in the night I added more terms to the b-file, and now the graph definitely is heading off to infinity. Roughly like e^(n/10)." --And I also think my analysis can be made more definitive (although still nonrigorous) as follows. problem: can Propp/Asimov's sequences f[n] = CorePart( f[n-1]+f[n-2] ) ever (with suitable starting integers) diverge to infinity without instead falling into a finite length cycle? Here CorePart(X) means the product of all the primes inside X's factorization, e.g. CorePart( 2*3*3*5*7*7*7*7 ) = 2*3*5*7. (Is that what Asimov meant?) If we model the X as "random" and ask about factors of P inside them (P=prime) then the chance X has exactly K factors of P inside it (K>=0) is exactly (P-1) * P^(-K-1) and then max(K-1, 0) of those factors need to be removed from X. So the expected additive reduction in ln(X) when we remove those factors is DELTA = DOUBLESUM( (K-1)*ln(P)*(P-1)*P^(-K-1), summed over primes P and integers K>=2 ). We can evaluate the sum over K in closed form, then the remaining sum over prime P is done numerically: DELTA = SUM( ln(P)/ [(P-1)*P], primes P ) =0.7554 meanwhile the increase in ln(X) due to the Fibonacci recurrence should be upper bounded by ln(2) = 0.6931 so it seems that the expected decrease in ln(X) ought to outweigh the expected increase due to summing, and therefore with "probability=1" this analysis would predict NON-growth to infinity and hence ultimate cycling. Exactly the opposite of Sloane's empirical computer finding. So evidently something is wrong with my cheesy probability model. And sure enough, examining Sloane's computer output https://oeis.org/A165911/b165911.txt we see that his numbers are NOT random uniform mod 2. Instead they are odd,odd,even,odd,odd,even,odd,odd,even... hence even only 1/3 of the time, not 1/2 as would naively be expected. Can other modular patterns be found (e.g. mod 3, etc)? Probably just a few such patterns will suffice to make the probability argument then reach the correct prediction. Maybe. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The classical "Pisano periods" (A001175) (an easily remembered name from the 1960's) give the period of Fib(n) mod n, and one can see that Fib_n has period 3 mod 2, period 8 mod 3, period 6 mod 4, but after that the periods get larger. So probably only the mod 2 effect will be significant
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let sk(N) mean the squarefree kernel (aka radical) of the integer N > 0. I.e., sk(N) = the product of all distinct prime factors of N. Then as regards the sequence defined by ----------------------------------------------- f(0) = 0, f(1) = 1, (*) f(N) = sk( f(N-1) + f(N-2) ), N >= 2 ----------------------------------------------- , precisely because as of 2009, this very sequence was already in OEIS, from Franklin T. Adams-Watters — I don't think it's appropriate that anyone else's name be associated with it. (Unless of course someone else discussed this even earlier.) I don't want to be immortalized in mathematics along with Kirmse <https://books.google.com/books?id=p4o-Uf-i-IUC&pg=PA26&lpg=PA26&dq=kirmse's+mistake&source=bl&ots=WB1X-E17tp&sig=2HBv_kW6BaI_A08soW1vizzaWOc&hl=en&sa=X&ved=0ahUKEwj20d_hj8fMAhVL9GMKHbmdCaoQ6AEINjAD#v=onepage&q=kirmse's%20mistake&f=false> by something called "Asimov's mistake" !!! * * * On the other hand, I guess the sequence defined by (*) but with arbitrary starting values f(0), f(1) is up for grabs. Question: --------- Are there any positive integers f(0) and f(1) that lead to a periodic sequence, as defined by (*) above? ((( And of course this generalizes to the same idea but with (*) replaced by (**) f(n) = sk( f(N-1) + ... + f(N-K) ), N >= K , with starting values supplied for f(1), ..., f(K). ))) —Dan
On May 6, 2016, at 2:31 PM, Neil Sloane <njasloane@gmail.com> wrote:
The classical "Pisano periods" (A001175) (an easily remembered name from the 1960's) give the period of Fib(n) mod n, and one can see that Fib_n has period 3 mod 2, period 8 mod 3, period 6 mod 4, but after that the periods get larger. So probably only the mod 2 effect will be significant
On 5/7/2016 12:28 AM, Dan Asimov wrote:
(*) f(N) = sk( f(N-1) + f(N-2) ), N >= 2
[where sk(n) is the squarefree kernel, or radical, of n]
Question: --------- Are there any positive integers f(0) and f(1) that lead to a periodic sequence, as defined by (*) above?
I already mentioned some simple examples that arise where f(0) and f(1) are not coprime: 2, 2 (period 1) 3, 3, 6, 3, 3, 6 (period 3) 5, 10, 15, 5, 10, 15 (period 3) There are many others; in particular, f(0) = f(1) = 2k (k odd, squarefree) always generates a constant sequence and any two initial values that are both even will result in an eventually constant sequence (an easy exercise). On the other hand, it seems that sequences with a common factor which is a larger prime may grow indefinitely. f(0) = f(1) = 17 seems like a borderline example; it has gradual rises mixed with teasing falls, but (for 2000 terms, at least) achieves net growth (up to 52 digits). I have since found three examples of periodic sequences starting with coprime initial values. Here they are: 15 146 161 307 78 385 463 106 569 (period 9) 222 1589 1811 170 1981 717 2698 3415 6113 2382 8495 10877 9686 20563 10083 30646 3133 33779 4614 38393 43007 4070 47077 17049 64126 16235 26787 6146 32933 39079 36006 75085 111091 5818 5083 10901 (period 46) 770 559 1329 118 1447 1565 1506 3071 4577 478 5055 5533 5294 1203 6497 (period 15) -- Fred W. Helenius fredh@ix.netcom.com
Fred — very cool! And mysterious! Apologies for overlooking your previous post on the matter. —Dan
On May 6, 2016, at 10:28 PM, Fred W. Helenius <fredh@ix.netcom.com> wrote:
On 5/7/2016 12:28 AM, Dan Asimov wrote:
(*) f(N) = sk( f(N-1) + f(N-2) ), N >= 2
[where sk(n) is the squarefree kernel, or radical, of n]
Question: --------- Are there any positive integers f(0) and f(1) that lead to a periodic sequence, as defined by (*) above?
I already mentioned some simple examples that arise where f(0) and f(1) are not coprime:
2, 2 (period 1) 3, 3, 6, 3, 3, 6 (period 3) 5, 10, 15, 5, 10, 15 (period 3)
There are many others; in particular, f(0) = f(1) = 2k (k odd, squarefree) always generates a constant sequence and any two initial values that are both even will result in an eventually constant sequence (an easy exercise). On the other hand, it seems that sequences with a common factor which is a larger prime may grow indefinitely. f(0) = f(1) = 17 seems like a borderline example; it has gradual rises mixed with teasing falls, but (for 2000 terms, at least) achieves net growth (up to 52 digits).
I have since found three examples of periodic sequences starting with coprime initial values. Here they are:
15 146 161 307 78 385 463 106 569 (period 9)
222 1589 1811 170 1981 717 2698 3415 6113 2382 8495 10877 9686 20563 10083 30646 3133 33779 4614 38393 43007 4070 47077 17049 64126 16235 26787 6146 32933 39079 36006 75085 111091 5818 5083 10901 (period 46)
770 559 1329 118 1447 1565 1506 3071 4577 478 5055 5533 5294 1203 6497 (period 15)
-- Fred W. Helenius fredh@ix.netcom.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Aha, I see it now. For an infinite set of primes P, a sequence obeying the fibonacci recurrence ought to exist, which is never zero modulo P. Therefore, never divisible by P or P^2. Therefore, my "random" model will not apply to those prime moduli and you'll never need to divide out powers of those P to keep it squarefree. When this realization is added to the probability model, it should easily suffice to make it nonrigorously clear that the thing will blow up to infinity, if appropriate starting integers are used. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (5)
-
Dan Asimov -
Dan Asimov -
Fred W. Helenius -
Neil Sloane -
Warren D Smith