wu :: forums
wu :: forums - Recurrence relation divisibility

Welcome, Guest. Please Login or Register.
Jun 24th, 2018, 4:10am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, SMQ, Grimbal, Icarus, william wu, Eigenray, towr)
   Recurrence relation divisibility
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Recurrence relation divisibility  (Read 2761 times)
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Recurrence relation divisibility  
« on: May 21st, 2003, 1:51pm »
Quote Quote Modify Modify

Let a1 = 1, and an = (n - 1)an-1 + 1, for n > 1.
 
For what values of n is an divisible by n?
IP Logged

Nick's Mathematical Puzzles
visitor
Guest

Email

Re: Recurrence relation divisibility  
« Reply #1 on: May 22nd, 2003, 6:14am »
Quote Quote Modify Modify Remove Remove

Well, my calculator could only go up to 85, but I got the numbers 1,2,4,5,10,13,20,26,37,52,65,74. There seems to be some pattern there but I don't know if it can be formalized.
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Recurrence relation divisibility  
« Reply #2 on: May 23rd, 2003, 9:42pm »
Quote Quote Modify Modify

I haven't gotten very far with it, but it might help to express
 
an = SUMk=0n-1 (n-1)!/k!
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
hyperdex
Newbie
*





   


Gender: male
Posts: 2
Re: Recurrence relation divisibility  
« Reply #3 on: May 27th, 2003, 1:15pm »
Quote Quote Modify Modify

Using Icarus's formula it is easy to show that if p|n then a_p and a_n are congruent mod p.  This means that if n|a_n and p|n, then p|a_p.
 
There appear to be very few primes p such that p|a_p.  I'm running a test for p<100000 and so far I've found 2, 5, 13, 37, 463, and 83507.  Also note that 4|a_4. This means that any integer that is a product of any subset of the odd primes listed here along with 1, 2, or 4 will satisfy the divisibility condition.  
 
I  wouldn't be surprised if the number of such n is finite seeing as the density of good primes is so small.  I would be surprised if there were an easy way to tell whether p is a prime such that p|a_p without actually calculating a_p mod p.
 
Cheers,
 
Dave
 
After thinking about this a bit more, I would be surprised if the number of primes such that p|a_p were finite.  Handwavingly, we would expect that the probability that a given prime p satisfies p|a_p would be roughly 1/p.  This means that the expected number of primes <n with p|a_p would be \sum_{p<n} 1/p which is approximately ln(ln n).  Since this goes to infinity with n (albeit slowly), we would expect the number of primes to be infinite.
 
I'd still be surprised if there were an easy test to check whether p|a_p.
 
 
Update:  I found all of the p's less than 800000 with p|a_p and in addition to the above primes found 306759, 412021, and 466123.  The number of primes seems less dense than my handwaving argument would imply, but perhaps my argument was wrong.
 
« Last Edit: May 28th, 2003, 12:22pm by hyperdex » 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