90/12/28
To: Dr. Clifford A. Pickover, Personal Programs
From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070
Enclosures: 1) MS-DOS disk containing Juggler programs
Dear Clifford,
This letter is in response to your Juggler Sequence challenge in
Algorithm 1.7, November 1990. The main challenge is to prove your
conjecture that all juggler sequences fall to 1. I did not prove
this one way or another, but assume there is a juggler sequence
that settles down to repeat the set of L numbers 1 < n = x[0],
x[1], . . ., x[L-1], x[L] = x[0]. For this to happen the ratio of
up to down movements would have to be close to p = Ln(2)/Ln(3/2)
÷ 1.7095. For instance 12 ups and 7 downs are in approximately
this ratio (12/7 ÷ 1.7143). If it were not for truncating to
integers each step, 12 ups and 7 downs would be the same as raising
x[0] to the (3/2)^12 * (1/2)^7 ÷ 1.0136 power.
If we were allowed to break the rules of when to go up, x <-
[x^(3/2)], and when to come down, x <- [x^(1/2)], we could easily
find sequences. For example, 3, 5, 11, 3, but we broke the rule
on 11, going down instead of up. Another: 9, 27, 140, 11, 36, 216,
14, 52, 374, 19, 82, 9, but we broke the rules 3 out of 11 times.
As x[0] gets larger, the length of this sequences, even if you
break the rules, is forced to get larger. A 19 length sequence of
12 ups and 7 downs cannot work for x[0] larger than 73. For x[0]
larger than this the shortest feasible sequence is 53 ups and 31
downs. If even and odd numbers are generated by the true juggler
sequence in a pseudo random way, a 52, 31 sequence is 2.4 standard
deviations from the expected 50% up, 50% down sequence. And, the
52, 31 sequence does not stay feasible as x[0] gets larger. As
x[0] gets larger the feasible sequences get longer and the
probability of matching the ups and downs becomes smaller. If
there is a counter example to the conjecture it will be very hard
to find.
There were a couple of typos in the article on page 7. The
sequence 3, 5, 11, 36, 6, 2, 1 had the 36 missing. In the next
sequence the number 233046 was written as 2333046.
You asked why some numbers produce fairly long sequences. The
sequence that starts with n = 37 starts with 4 consecutive up
motions and is the first integer to do so. When n is 173 there is
a group of 8 consecutive up motions. For n = 193 there is a 7 and
a 6 length sequence of consecutive up motions. There is no reason
other than it is bound to happen, we will find long sequences when
the ups dominate the downs early in a sequence.
All sequences that fall to 1 must terminate in 2, 1 because 2 is
the only integer that falls to 1. The only integers that fall to
2 are 4, 6, and 8. In general, the only integers that fall to x
are the even integers 2i where x^2 <= 2i < (x+1)^2. No integers
rise to 2. So, all sequences that fall to 1 terminate in one of
three ways: 4, 2, 1; 6, 2, 1; or 8, 2, 1.
I have written 4 programs to investigate these juggler sequences
and have included them on the disk enclosed, including all source
code and saved output. The program Juggler0 repeats the results
of your article by generating all juggler sequences with n <= 200.
The maximum number of decimal digits, DM, needed to represent the
largest number in each sequence is also computed. For n = 193, DM
= 271. To compute the juggler sequence starting with 193 you need
to be able to handle an even number in the sequence with 271
decimal digits. An example output is:
37 -> 225 -> 3375 -> 1,96069 -> 868,18724 -> 9317 -> 8,99319 ->
8528,46071 -> 2490,61144,55136 -> 49,90602 -> 2233 -> 1,05519
-> 342,76462 -> 5854 -> 76 -> 8 -> 2 -> 1;
L=18, DM=14, New max L, New max DM
The program Juggler1 shows juggler sequences ups and downs. An
example of the output is:
n=37 UUUUDUUUDDUUDDDDD L=18 DM=14, New max L, New max DM
The program JugglerL finds juggler sequences with Max L > all
previous Max L. An example output is:
n=1119 L=76 DM=271, New max L
UDUUUDUUUUUUUDUUUDDUDDUUUUUUDDDUUUDUUDDUUUUUDUUUUDDUUDUUDUDDUUDUU
DDUDDDDDDD
The program JugglerM finds juggler sequences with Max x > all
previous Max x. An example output is:
x_zero: Max_x (digits in Max_x)
173: 44,50608,86021,06782,34719,66493,09188,17118,56465,
90642,89879,58622,83901,54864,37851,14108,64886 (82)
193: 67435,...,59090 (271)
I have extended the search for a juggler sequence that does not
fall to 1, to all x[0] less than 48443 and none could be found.
A max x with 45391 decimal digits was generated during the search.
The sequence with x[0] = 48443 has a DM > 57323 decimal digits.
Sincerely,
Harry
times since October 20, 2004.