wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi) riddles >> hard >> Recurrence relation divisibility (Message started by: NickH on May 21st, 2003, 1:51pm)  Title: Recurrence relation divisibility Post by NickH on May 21st, 2003, 1:51pm Let a1 = 1, and an = (n - 1)an-1 + 1, for n > 1.For what values of n is an divisible by n? Title: Re: Recurrence relation divisibility Post by visitor on May 22nd, 2003, 6:14am Well, my calculator could only go up to 85, but I got the numbers [hide]1,2,4,5,10,13,20,26,37,52,65,74[/hide]. There seems to be some pattern there but I don't know if it can be formalized. Title: Re: Recurrence relation divisibility Post by Icarus on May 23rd, 2003, 9:42pm I haven't gotten very far with it, but it might help to expressan = SUMk=0n-1 (n-1)!/k! Title: Re: Recurrence relation divisibility Post by hyperdex on May 27th, 2003, 1:15pm 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,DaveAfter 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