Re: A Recreational Endeavour
- To: mathgroup at smc.vnet.net
- Subject: [mg8762] Re: [mg8751] A Recreational Endeavour
- From: Hans Havermann <haha at astral.magic.ca>
- Date: Sun, 21 Sep 1997 20:51:06 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Dr. Wouter L.J. Meeussen writes:
>If you put both x and y in the returned answer, then you get a "real"
>permutation as result : containing all integers from 1 up to 4+3n, the first
>n from x, the rest in y.
Thank you for all this. It will take me a little time to go through it. The
algorithm is perhaps a little more understandable from the perspective of
its origin...
Row01: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
Row02: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
Row03: 4 2 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
Row04: 6 2 7 4 8 9 10 11 12 13 14 15 16 17 18 ...
Row05: 8 7 9 2 10 6 11 12 13 14 15 16 17 18 19 ...
Row06: 6 2 11 9 12 7 13 8 14 15 16 17 18 19 20 ...
Row07: 13 12 8 9 14 11 15 2 16 6 17 18 19 20 21 ...
Row08: 2 11 16 14 6 9 17 8 18 12 19 13 20 21 22 ...
Row09: 18 17 12 9 19 6 13 14 20 16 21 11 22 2 23 ...
Row10: 16 14 21 13 11 6 22 19 2 9 23 12 24 17 25 ...
To generate Row'n+1' from Row'n': expel the n-th number (it is these
expelled "diagonal" numbers that comprise my sought-after set); *rewrite*
beginning with the first number to the right of the dropped number followed
by the first number to the left (if any); then the second number to the
right of the dropped number followed by the second number to the left (if
any); and so on. The idea was proposed by Clark Kimberling as problem #1615
in the Canadian "Crux Mathematicorum" in 1991. He asks:
(a) Is 2 eventually expelled?
(b) Is every positive integer eventually expelled?
In the March 1992 issue of Crux (Vol.18, #3), a solution to part (a) is
given by Iliya Bluskov, who developed an algorithm for the general case and
applies it for all n < 51. He notes that '19' is expelled in Row 49595.
The editor of Crux comments on the general case, citing Richard and Andy
Guy as having done work on it. Specifically, they had shown "that every
integer up to 1200 is eventually expelled" with, for instance, '669' being
expelled in Row 653494691. Richard also found several infinite "families"
of expelled integers.
*My* interest in all this: Having calculated a 4491 element set for x, we
notice:
Do[If[x[[i]]==i,Print[i]],{i,1,Length[x]}]
1
4
8
14
171
This immediately suggests:
Do[If[x[[i]]<=Length[x],If[x[[i]]!=i,If[x[[x[[i]]]]==i,Print[i]]]],{i,1,
Length[x]}]
813
985
In other words x[[813]]=985 and x[[985]]=813.
So now I'm thinking: what other "loops" like this can we discover? My
guess: not many (without some serious computing power). Some years ago, in
Basic, I had calculated quite a few terms of the "loop" in which '2' finds
itself [... 1523, 43, 25, 2, 3, 5, 10, 9, 20, ... ]. It is possible
*algorithmically* to go forward (or backward) along this loop finding the
next (or previous) term. I love the *asymmetry* of this sequence: Going
forward, the next number is always guaranteed, never more than three times
as large. Going backwards, who knows? There may not even be a previous
number! We think we can understand why the numbers must get bigger (on
average) as we move forward, *but* we must remind ourselves that we have
gotten to '2' from some very large "ancestor" in the same process of moving
forward! :-)
I lost all my primary data on this a couple of years ago in a hard-drive
crash. :-(
Hans Havermann
Rarebit Dreams
http://astral.magic.ca/~haha/rarebit.html