wu :: forums
« wu :: forums - Towers of 2's modulo n »
Welcome, Guest. Please Login or Register.
Nov 28th, 2024, 8:05pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium (Moderators: SMQ, Eigenray, towr, Grimbal, Icarus, william wu, ThudnBlunder)
   Towers of 2's modulo n		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Towers of 2's modulo n  (Read 574 times)
Michael Dagg
Senior Riddler
****






   


Gender: male
 Posts: 500
Towers of 2's modulo n  
« on: Feb 5th, 2008, 8:45am »		 Quote Quote Modify Modify
For  n > 2  show that
 
2^(2)^(2)...(2) } n  =  2^(2)^(2)...(2) } n-1  mod n
IP Logged
Regards,
Michael Dagg
Hippo
Uberpuzzler
*****





   


Gender: male
 Posts: 919
Re: Towers of 2's modulo n  
« Reply #1 on: Feb 5th, 2008, 2:28pm »		 Quote Quote Modify Modify
It's very simillar to 13^13^13^...13 question I have formulated recently. n->phi(n)->phi(phi(n))-> ... goes to 1 quickly
 
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_eas y;action=display;num=1200874487;start=0#11
« Last Edit: Feb 5th, 2008, 2:36pm by Hippo » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 1948
Re: Towers of 2's modulo n  
« Reply #2 on: Feb 5th, 2008, 2:33pm »		 Quote Quote Modify Modify
And a bit more difficult:
 
E(n+1) E(n)  mod pn,
 
where E(1) = 2; E(n+1) = 2E(n); and pn is the n-th prime.
 
Thus
 
2 | 4 - 2
3 | 16 - 4
5 | 65536 - 16
7 | 265536 - 65536
 
[The smallest prime which doesn't divide E(n+1) - E(n) is: 3, 5, 11, 23, 47, 283, 719, 1439, 2879, ...]
« Last Edit: Feb 5th, 2008, 2:49pm by Eigenray » IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
 Posts: 919
Re: Towers of 2's modulo n  
« Reply #3 on: Feb 5th, 2008, 2:41pm »		 Quote Quote Modify Modify
I thing the reasoning would be the same ... we are investigating the speed of convergence of the same "contraction" (only starting point and allowed length differs).
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 1948
Re: Towers of 2's modulo n  
« Reply #4 on: Feb 5th, 2008, 2:52pm »		 Quote Quote Modify Modify
But there's a complication due to the fact that k pn+1 does not imply that (k) pn.
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
 Posts: 919
Re: Towers of 2's modulo n  
« Reply #5 on: Feb 6th, 2008, 1:02am »		 Quote Quote Modify Modify
Yes, it cannot be simple induction. ... I would study the sequence p_k and phi^{(k)}(n) independently ...
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board