[math-fun] Propp's "squarefree-fibo" sequence
Well, can Propp's sequences f[n] = SquareFreePart( f[n-1]+f[n-2] ) ever (with suitable starting integers) diverge to infinity without instead falling into a finite length cycle? Here SquareFreePart(X) means the product of all the primes that had odd powers inside X's factorization, e.g. SquareFreePart( 2*3*3*5*7*7*7*7 ) = 2*5. If we model the X as "random" then with chance 1/4 they contain a factor of 4 that will be removed, with chance 1/9 they contain a factor 9, etc. So ln(X) is going to decrease due to these removals, by an expected additive amount DELTA with DELTA <= SUM_{k>1} k^(-2) * ln(k^2) = 1.875096508631687507405148... The expected decrease amount also is lower bounded by the same sum but summed over prime k only: DELTA > 0.9861. Also note, the "probability distribution" of DELTA has finite variance. Meanwhile, ln(X) is going to grow due to the Fibonacci-like recurrence, by some amount presumably less than ln(2) = 0.693147180559945 in "expectation." A lower bound on the expected decrease amount is clearly greater than an upper bound on the expected increase amount. Therefore by the strong law of large numbers" of probability theory, it "follows" that increase of ln(f[n]) to infinity is impossible. This of course would only be a proof if the f[n] really behaved "randomly," which is bogus, but it is enough to make the "it always cycles" conjecture plausible. I tend to doubt Propp's stronger conjecture that only one particular limit cycle is possible; and to disprove that, it would suffice to find a single counterexample starting 2-tuple. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Actually, simply multiply every element of Propp's conjectured unique limit cycle, by P, where P is any large enough prime. Result is a different limit cycle. So Propp's conjecture of one particular limit cycle always happening, is definitely wrong. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Yup! You and Fred H. are definitely right about that. I should have spent an extra minute actually thinking instead of just coding and executing... Jim On Thu, May 5, 2016 at 1:38 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Actually, simply multiply every element of Propp's conjectured unique limit cycle, by P, where P is any large enough prime.
Result is a different limit cycle.
So Propp's conjecture of one particular limit cycle always happening, is definitely wrong.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dan Asimov's misinterpretation of Propp's notion of "squarefree part" is still a perfectly good problem. If we redo my probabilistic heuristic analysis for that 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" then with chance 1/4 they contain a factor of 2 that will be removed, with chance 1/8 a fatcor 4 is removed, chnace 1/9 a factor 3 is removed, etc. So ln(X) is going to decrease due to these removals, by an expected additive amount DELTA with DELTA <= SUM_{k>1} SUM_{q>0} k^(-1-q) * ln(k^q) = 1.77 The expected decrease amount also is lower bounded by the same sum but summed over prime k only and demanding q=1 only: DELTA > 0.49. Also note, the "probability distribution" of DELTA has finite variance. Meanwhile, ln(X) is going to grow due to the Fibonacci-like recurrence, by some amount presumably less than ln(2) = 0.693147180559945 in "expectation." So... it looks unclear whether Asimov's problem-version can go infinite and avoid a cycle, in this probability model. Need less-sloppy upper and lower bounds on DELTA. It seems to be a close thing, when I try to be less sloppy; e.g. one of my less-sloppy lower bounds was 0.642 which is quite close to 0.693. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
For starting values f(0) = i, f(1) = j for [i,j] in {[1, 9], [5, 8], [8, 7], [9, 4], [9, 10]} the elements f(0),f(1),...,f(1000) are distinct using f(n) = CorePart( f(n-1)+f(n-2)). On Thu, May 5, 2016 at 2:50 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Dan Asimov's misinterpretation of Propp's notion of "squarefree part" is still a perfectly good problem.
If we redo my probabilistic heuristic analysis for that 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" then with chance 1/4 they contain a factor of 2 that will be removed, with chance 1/8 a fatcor 4 is removed, chnace 1/9 a factor 3 is removed, etc. So ln(X) is going to decrease due to these removals, by an expected additive amount DELTA with DELTA <= SUM_{k>1} SUM_{q>0} k^(-1-q) * ln(k^q) = 1.77 The expected decrease amount also is lower bounded by the same sum but summed over prime k only and demanding q=1 only: DELTA > 0.49. Also note, the "probability distribution" of DELTA has finite variance.
Meanwhile, ln(X) is going to grow due to the Fibonacci-like recurrence, by some amount presumably less than ln(2) = 0.693147180559945 in "expectation."
So... it looks unclear whether Asimov's problem-version can go infinite and avoid a cycle, in this probability model. Need less-sloppy upper and lower bounds on DELTA. It seems to be a close thing, when I try to be less sloppy; e.g. one of my less-sloppy lower bounds was 0.642 which is quite close to 0.693.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
James Propp -
W. Edwin Clark -
Warren D Smith