Author 
Topic: Recurrence relation divisibility (Read 2940 times) 

NickH
Senior Riddler
Gender:
Posts: 341


Recurrence relation divisibility
« on: May 21^{st}, 2003, 1:51pm » 
Quote Modify

Let a_{1} = 1, and a_{n} = (n  1)a_{n1} + 1, for n > 1. For what values of n is a_{n} divisible by n?


IP Logged 
Nick's Mathematical Puzzles



visitor
Guest


Re: Recurrence relation divisibility
« Reply #1 on: May 22^{nd}, 2003, 6:14am » 
Quote Modify
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:
Posts: 4863


Re: Recurrence relation divisibility
« Reply #2 on: May 23^{rd}, 2003, 9:42pm » 
Quote Modify

I haven't gotten very far with it, but it might help to express a_{n} = SUM_{k=0}^{n1} (n1)!/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:
Posts: 2


Re: Recurrence relation divisibility
« Reply #3 on: May 27^{th}, 2003, 1:15pm » 
Quote Modify

Using Icarus's formula it is easy to show that if pn then a_p and a_n are congruent mod p. This means that if na_n and pn, then pa_p. There appear to be very few primes p such that pa_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 4a_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 pa_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 pa_p were finite. Handwavingly, we would expect that the probability that a given prime p satisfies pa_p would be roughly 1/p. This means that the expected number of primes <n with pa_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 pa_p. Update: I found all of the p's less than 800000 with pa_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 28^{th}, 2003, 12:22pm by hyperdex » 
IP Logged 



