| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
I was thinking about the 3n+1 problem (q.v.) which I'll review for those
of you that don't know what q.v. means, and for those of you that do but
are suffering from VAXnotes inability to *quickly* search for a topic.
The problem is: take a positive number, if odd, multiply by 3 and add 1,
else divide by 2, and repeat unless you reach 1. Prove that you'll always
reach 1.
I happened to be at a friends place, playing with their son and his
computer. I quickly typed in a BASIC program that prints out the
sequences.
Being a kid, he almost instantly entered a negative number. Being a
quick program, I hadn't programmed for that.
Well, some interesting sequences emerged, and it piqued my curiosity (is
that the right word ?)
I realize now that studying negative numbers in the 3n+1 problem is
isomorphic to studying positive numbers in the 3n-1 problem.
So, I started studying the 3n-1 problem. Namely, if odd, 3n-1 else n/2,
repeat until pattern emerges.
Interesting hypothesis here:
All numbers lead to one of the following three loops:
1,2
5,14,7,20,10
17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34
I've got a program written in C, which I'll publish at the end of this
report, that allows studying the sequences.
Here is the summary of what I observe from running the program:
o The pattern of when each of the sequences comes up seems random.
(try setting ALL_FLAG to 1 in debugger to see pattern)
o The path for the number 149345 is too large for the 19-digit accuracy
available on the VAX, so I don't yet know what happens to that number.
o All other numbers from 1 to 500000 seem to pave a path to one
of the above sequences.
I suspect this 3n-1 problem is as "hard" as the 3n+1 problem, although different
since in the 3n+1 problem seems to pave all numbers to 1, but 3n-1 seems
to pave all numbers to THREE different loops.
What about other kn+j problems ?
Here's my C program. I'll sign off first, then you can read the program
on your own.
Bye.
/Eric
----------------------------------------------------
#define max_mem 500000
#define max_s 500000
double float num, n, mem[max_mem], new_n, old_n, s[max_s];
int i, first_rep, second_rep, min_rep, run_flag, odd_flag, new_seq_flag, qs, q,
ino2, all_flag=0, ones=0, fives=0, seventeens=0;
main ()
{
qs = 0;
for (num=1; num<500000; num++)
{
n = num; q = 1; run_flag = 1;
mem[0] = n;
while (run_flag)
{
odd_flag = 1;
if ((ino2=n/2)!=n/2) new_n = 3*n - 1; else new_n = n/2, odd_flag = 0;
if (odd_flag) old_n = (new_n + 1) / 3; else old_n = new_n*2;
if (old_n != n)
{
printf ("Skipping %f due to overflow.\n", num);
run_flag = 0;
}
else
{
n = new_n;
if (q >= max_mem)
{
printf ("Out of memory.\n");
exit ();
}
mem[q++] = n;
if (find_twice ())
{
find_min (first_rep, second_rep);
new_seq_flag = 1;
for (i=0; i<qs; i++) if (s[i] == mem[min_rep]) {new_seq_flag = 0;break;}
if (all_flag) pchar ();
if (new_seq_flag)
{
pseq ();
if (qs >= max_s)
{
printf ("Out of room for new sequences.\n");
exit ();
}
s[qs++] = mem[min_rep];
}
run_flag = 0;
}
} /* end of processing if not overflow */
} /* end of processing for particular n */
} /* end of loop over n */
} /* end of main */
find_twice ()
{
for (first_rep=0; first_rep<q-1; first_rep++)
if (mem[first_rep] == n)
{
second_rep = q-1;
first_rep++;
return 1;
}
return 0;
}
find_min ()
{
double float min = mem[first_rep];
int i;
min_rep = first_rep;
for (i=first_rep; i <= second_rep; i++)
if (mem[i] < min) min = mem[i], min_rep = i;
}
pseq ()
{
printf ("%f ", num);
i = min_rep;
do
{
printf ("%f,", mem[i]);
i++;
if (i > second_rep) i = first_rep;
}
while (i != min_rep);
printf ("\n");
}
pchar ()
{
switch ((int)mem[min_rep])
{
case 1: printf ("."); ones++; break;
case 5: printf ("*"); fives++; break;
case 17: printf ("\\"); seventeens++; break;
default:
printf ("\nUnknown sequence!\n");
pseq ();
exit ();
}
}
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 695.1 | all numbers 1-500000 map to 1,5, or 17 | VIDEO::OSMAN | type video::user$7:[osman]eric.six | Thu Apr 30 1987 18:00 | 11 |
I have verified the 149345 and other numbers that cause overflow.
I used some DCL procedures that I wrote that do BIGNUM integer
arithmetic.
The summary is that *all* numbers from 1 to 500000 map to
1, 5, or 17.
Is this true for all numbers ? Is it as hard to prove as
the yet unproven 3n+1 problem ?
/Eric
| |||||
| 695.2 | CLT::GILBERT | eager like a child | Mon May 04 1987 13:04 | 46 | |
Consider a three-cycle:
( 3 ( 3 (3n-1)/2^a - 1 )/ 2^b - 1 ) / 2^c = n
3 a+b+c a+b a 2
3 n = 2 n + 2 + 3 2 + 3
In general, for an m-cycle, we have:
m a(1)+...+a(m) a(1)+...+a(m-1) a(1)+...+a(m-2)
(3 - 2 ) n = 2 + 3 2 + ... +
k a(1)+...+a(m-1-k) m-1
+ 3 2 + ... + 3
We would like to find integers n,m,a(1)..a(m) (with the a(i) >= 1) that
satisfy this equation.
For example, with the 5,7,... cycle we have:
2 1+2 1 2 2+1 2
(3 - 2 ) 5 = 2 + 3, and (3 - 2 ) 7 = 2 + 3.
And for 17,... cycle,
7 1+1+1+2+1+1+4 1+1+1+2+1+1 1+1+1+2+1 2 1+1+1+2
(3 - 2 ) 17 = 2 + 3 2 + 3 2 +
3 1+1+1 4 1+1 5 1 6
+ 3 2 + 3 2 + 3 2 + 3 , or,
7 11 7 6 2 5 3 3 4 2 5 6
(3 - 2 ) 17 = 2 + 3 2 + 3 2 + 3 2 + 3 2 + 3 2 + 3 , or
simply 139 * 17 = 2363.
Note that 3^m must be larger than 2^(sum(a(i)), and that the right-hand
side of the above equations has the bounds:
m m a(1)+...+a(m-1)
3 - 2 <= 2 + ...
k a(1)+...+a(m-1-k)
+ 3 2 + ...
m-1 m-1 m-1 sum(a(i))-m+1 m+1
+ 3 <= (3 - 2 ) 2 + 3
Given m, sum(a(i)), these bounds, and the requirement that n > 500000,
it should be possible to quickly search for other 'cycles' or show that
cycles of certain lengths simply don't exist.
| |||||
| 695.3 | CLT::GILBERT | eager like a child | Mon May 04 1987 13:44 | 19 | |
Another approach is to realize that the '-1' in '3n-1' has a very
negligable effect when n is large. Since n <= 500000 has been
completely visited, we can approximate the m-cycle, letting:
3*n-1 = 3*n*(1-e), 0 < e < 1/1500000.
We want:
m s
3 n (1-e(1)) (1-e(2)) ... (1-e(m)) = 2 n
where s = sum(a(i)) from the previous reply.
We must have:
m m s m
3 (1-1/15000000) < 2 < 3
Some simple math shows that there are no m-cycles for m < 665, except
for those described in .0. Note that m=665, s=1054 shows some slight
promise of producing a cycle.
| |||||
| 695.4 | my program had a bug in it, but no dif. conclusions | VIDEO::OSMAN | type video::user$7:[osman]eric.six | Mon May 04 1987 15:56 | 126 |
My program had a serious bug in it. Nothing excited comes of all this,
though. The fixed version still only finds cycles of 1, 5, and
17.
The bug was that I was incorrectly determining whether a double
floating point number was odd or not.
The corrected program successfully verifies ALL numbers from 1-500000,
without getting any overflows.
Here's the program:
#define max_mem 500000
#define max_s 500000
double float num, n, mem[max_mem], new_n, old_n, s[max_s], k=3, j= -1, no2;
int i, first_rep, second_rep, min_rep, run_flag, odd_flag, new_seq_flag, qs, q,
all_flag=0, ones=0, fives=0, seventeens=0;
main ()
{
qs = 0;
for (num=1; num<500000; num++)
{
n = num; q = 1; run_flag = 1;
mem[0] = n;
while (run_flag)
{
double float mth$dint ();
odd_flag = 1;
no2 = n/2;
if (no2 != mth$dint (&no2)) new_n = k*n + j; else new_n = n/2, odd_flag = 0;
if (odd_flag) old_n = (new_n - j) / k; else old_n = new_n*2;
if (old_n != n)
{
printf ("Skipping %f due to overflow.\n", num);
run_flag = 0;
}
else
{
n = new_n;
if (q >= max_mem)
{
printf ("Out of memory.\n");
exit ();
}
mem[q++] = n;
if (find_twice ())
{
find_min (first_rep, second_rep);
new_seq_flag = 1;
for (i=0; i<qs; i++) if (s[i] == mem[min_rep]) {new_seq_flag = 0;break;}
if (all_flag) pchar ();
if (new_seq_flag)
{
pseq ();
if (qs >= max_s)
{
printf ("Out of room for new sequences.\n");
exit ();
}
s[qs++] = mem[min_rep];
}
run_flag = 0;
}
} /* end of processing if not overflow */
} /* end of processing for particular n */
} /* end of loop over n */
} /* end of main */
find_twice ()
{
for (first_rep=0; first_rep<q-1; first_rep++)
if (mem[first_rep] == n)
{
second_rep = q-1;
first_rep++;
return 1;
}
return 0;
}
find_min ()
{
double float min = mem[first_rep];
int i;
min_rep = first_rep;
for (i=first_rep; i <= second_rep; i++)
if (mem[i] < min) min = mem[i], min_rep = i;
}
pseq ()
{
printf ("%f ", num);
i = min_rep;
do
{
printf ("%f,", mem[i]);
i++;
if (i > second_rep) i = first_rep;
}
while (i != min_rep);
printf ("\n");
}
pchar ()
{
switch ((int)mem[min_rep])
{
case 1: printf ("."); ones++; break;
case 5: printf ("*"); fives++; break;
case 17: printf ("\\"); seventeens++; break;
default:
printf ("\nUnknown sequence!\n");
pseq ();
exit ();
}
}
| |||||
| 695.5 | CLT::GILBERT | eager like a child | Mon May 04 1987 22:05 | 100 | |
I tested numbers thru 6x10^8, and found no other cycles.
The program, FWIW, follows.
one_sec: .long -10*1000*1000,-1
.entry astrtn, ^m<>
decl r7
$setimr_s daytim=one_sec, astadr=astrtn
ret
.entry main, ^m<r2,r3,r4,r5>
calls #0, init_bv
calls #0, astrtn
movq #50*1000*1000, r4
bicl2 #3, r4
bisl2 #1, r4
clrl r7
10$: movq r4, r0
clrl r6
20$: incl r6
ashq #-1, r0, r2
addl2 r2, r0
adwc r3, r1
bvs 999$
blbs r0, 20$
30$: ashq #-1, r0, r0
blbc r0, 30$
cmpl r0, r4
bgequ 20$
tstl r1
bneq 20$
cmpl r6, r7
bgeq 50$
51$:
addl2 #4, r4
bvs 52$
movzwl r4, r0
bbs r0, b^bv, 51$
brb 10$
52$: movl #1, r0
ret
999$: bpt
50$: movq r0, -(sp)
pushl r6
pushl r4
pushab ctrstr
calls #3, g^util$output
movq (sp)+, r0
movl r6, r7
brb 51$
k_bits = 16
bv: .blkb 1@<k_bits-3>
.entry init_bv, ^m<>
movc5 #0, (sp), #0, #1@<k_bits-3>, bv
movl #1, r4
10$: movl #1@k_bits, r1
movl r4, r0
cmpl r0, r1
blss 11$
ret
11$: cmpl r1, #1@k_bits
blss 25$
;
; We have R1*n + R0 -- see what happens
;
blbs r1, 20$
mull2 #3, r0
mull2 #3, r1
decl r0
15$: ashl #-1, r0, r0
ashl #-1, r1, r1
blbs r1, 20$
blbc r0, 15$
brb 11$
20$: cmpl r1, #1@k_bits
bgeq 30$
25$: bbcs r4, bv, 30$
30$: addl2 #2, r4
brw 10$
ctrstr: .ascid /!UL = !-!XL, !UL iteration!%S/
.end main
| |||||
| 695.6 | My, how you've grown! | ZFC::DERAMO | Subscribe to NOTES Digest! | Mon May 04 1987 22:09 | 42 |
I only checked up to 20,000,000 (special thanks to VAX LISP
for the bignum arithmetic), with the same results.
I recorded the largest value reached before falling back to
the cycle, and the smallest starting value that reached it.
For example, the largest number that can be reached with an
initial value less than 153 is 4,376; but if you start with
153 then the chain will reach 33,212 at its highest.
1 2
3 8
5 20
9 56
17 272
33 488
65 1,640
129 4,376
153 33,212
321 132,860
1,425 166,376
1,601 262,712
1,889 826,688
3,393 835,436
4,097 1,915,328
6,929 2,879,552
8,193 3,188,648
10,497 5,816,936
11,025 80,439,500
18,273 88,884,056
28,161 390,092,456
74,585 954,501,248
85,265 1,021,838,024
149,345 9,675,843,500
337,761 9,725,840,912
558,341 78,312,864,044
839,429 78,492,315,980
1,022,105 90,720,534,764
1,467,393 6,586,151,865,824
7,932,689 14,066,009,972,588
8,612,097 30,541,433,029,400
Dan
| |||||