[seqfan] Re: Puzzle of David Wilson

Sun Mar 1 02:09:39 CET 2015

I finally found time to write some code for this puzzle, available on
github at <https://github.com/hvds/seq/tree/master/wilson>. The results
file shows my findings so far for rationals with denominators up to 30.

I'd found some solutions up to 26 elements long, but this one blows them
out of the water:

11/14 is solved in 73 steps by [
  168 2 28 1 4 2275 16 4 18 2
  9 3 1 234 7 1456 8 2 6 6
  116 2 16 2 6 1 2 10 18 2
  2 3 2 1165 11 2 1 21 1 75
  84 1 7 6 7 3 56 1 24 4
  15 1 162 1 1 4 11 1 2 1
  7 22 136 10 7 1 6 5 1 1
  1 5 1
]

This is the shortest sequence that solves 11/14, and the only solution
of that length, found by attempting a depth-first search to a limit of
80 (after calibrating with a breadth-first search to the limit of my
available RAM, which reached a depth of 62).

Now trying 9/11 with a maximum depth of 100 (which will take a week or
two), and 16/21 to depth 70 (which looks more likely to be solvable).

Hugo

Matthijs Coster <seqfan at matcos.nl> wrote:
:Hello Bob and all of them who are interested in the Puzzle,
:
:I started an experiment with r = 25/27. I decided to have a very small 
:set S, but then I continued with all fractions in S until the fractions 
:exceeded all the norm (i.e. the size of the denominator) which was fixed 
:at 10^80. As long the size of succeeders were smaller than the norm the 
:fractions were added to S. The result was that 8.2 % of the succeeder's 
:had smaller norms than the originals. Let No and Ns be the norms of 
:originals and succeeder respectively. I made a table of the quotients 
:floor(Ns/No) (increasing case) and floor(No/Ns) (decreasing case):
:
:Explanation: First column n; second column increasing case; third column 
:decreasing case
:1 72575 39547
:2 69859 13382
:3 60794 6670
:4 56907 4023
:5 55422 2628
:6 53012 1847
:7 51051 1410
:8 49402 1146
:9 43799 911
:10 32041 793
:11 31461 595
:12 30447 495
:13 29612 466
:14 28794 361
:15 27919 331
:16 27269 316
:17 26087 275
:18 25993 260
:19 25461 192
:20 24963 175
:21 24071 160
:22 23798 184
:23 23064 150
:24 22626 133
:25 22248 118
:26 21514 124
:27 21248 111
:28 20895 90
:29 3302 93
:30 0 2674
:
:Very remarkable are the enormous large numbers which appear in 
:floor(No/Ns):
:
:21043, 68249, 22535 and 139697
:
:It is rather comparable to the convergents of continued fractions.
:By the way, I didn't found a Wilson--chain.
:
:Best regards,
:
:--Matthijs Coster
:
:
:Bob Selcoe schreef op 28-1-2015 om 23:47:
:> Hi Matthijs and Seqfans,
:>
:> Thanks for writing the paper and citing me, Matthijs!   I will need 
:> time to review.
:>
:> One thing first - I'd be surprised if all real positive rational 
:> numbers < 1 didn't create Wilson-chains.
:>
:> Would you mind trying my "modular approach" with, say, 9/11?  It may 
:> require a somewhat different program - one that (I think) would 
:> eliminate many of the iterations required with the current program.
:>
:> Here, the first term (11/2) would be the last term in your current 
:> program, then just make a "modular chain" until you reach 2/11.
:>
:> So the first few steps are:
:>
:> R_(1-9/11) = 11/2 = 121/22.   9/11 = 18/22.   121 mod 18 = 15.
:>
:> R_(15/22) = 22/15 = 242/165.   9/11 = 135/165.   242 mod 135 = 107.
:>
:> R_(107/165) = 165/107 = 1815/1177.  9/11 = 963/1177.   1815 mod 963 = 
:> 852.
:> etc.
:>
:> So generally, when a/b > 1/2, the process is first find b^2 mod 
:> a(b-a), = a' and b(b-a) = b', then continue the process with b*b' mod 
:> a*a' = a'' and b*b' = b'', etc., until reaching (b-a)/b.
:>
:> (Of course, all fractions - and thus the a-primes and b-primes - may 
:> be in reduced form).
:>
:> Certainly, this doesn't preclude other possible Wilson-chains existing 
:> for 9/11 (as you've shown occurs with 7/9); but I think this 
:> particular approach can lead to more economical paths.  While it might 
:> take many steps, each step really is only one iteration; so I would 
:> think it wouldn't be too intense for the computer.  I would do this 
:> myself but I don't know the first thing about computer programming!
:>
:> Best,
:> Bob S.
:>
:>
:>
:> --------------------------------------------------
:> From: "Matthijs Coster" <seqfan at matcos.nl>
:> Sent: Wednesday, January 28, 2015 7:59 AM
:> To: "_Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
:> Subject: [seqfan] Puzzle of David Wilson
:>
:>> LS,
:>>
:>> For everybody who is interested in the puzzle of David Wilson (z -> z 
:>> + kr, or z -> 1/z).
:>> I wrote a paper with my results.
:>> See: http://www.matcos.nl/sequences/SeqFanPuzzle.pdf.
:>>
:>> Please send me your commands!
:>>
:>> Best regards,
:>>
:>> --Matthijs
:>>
:>>
:>>
:>> _______________________________________________
:>>
:>> Seqfan Mailing list - http://list.seqfan.eu/
:>>
:>
:> _______________________________________________
:>
:> Seqfan Mailing list - http://list.seqfan.eu/
:
:
:_______________________________________________
:
:Seqfan Mailing list - http://list.seqfan.eu/