Welcome to NRICH.

 
Prime pattern
By Amars Birdi on Saturday, July 28, 2001 - 12:54 pm:

Let un denote the number of ways of expressing n as the sum of positive integers regardless of the order of those integers.
So, u1 = 1, u2 = 2, u3 = 3, u4=5.

i.e.
1=1 (1 way)
2=2=1+1 (2 ways)
3=3=1+1+1=2+1 (3 ways)
4=4=1+1+1+1=3+1=2+2=2+1+1 (5 ways)

I just wanted to confirm that the pattern in this sequence of numbers is that they're prmes (it's just that my text book states that un can be expressed in terms of previous terms of the sequence, and I don't know of such a recurrence relation for prime numbers).

By Arun Iyer on Saturday, July 28, 2001 - 07:07 pm:

I think the above sequence is a Fibonacci sequence.Though I will check and answer later.

love arun

By Brad Rodgers on Sunday, July 29, 2001 - 12:59 am:

I think that u9=30. So not all of these are prime. Also, u5=7, so I don't think this is the Fibonacci series. Does your book give a reccurance realtionship? The only one I can think of is not really a formula, more of an algorithm, and involves summing all the previous uns then subtracting a number based upon certain conditions (these conditions being nearly as hard to determine as the number itself). I don't even think I could write this in relation in closed form.

On a similar note, Ramanujan did some work in this area, and I think that he found that u5n+4=5k for n and k integers, though I have no idea how he proved this.

By Amars Birdi on Sunday, July 29, 2001 - 01:17 pm:

On dear, I was hoping that there would be a nice and simple recurrence relation. Perhaps you could show me a simple program that could give out the various values of un (it's just that it's annoying to find un values by hand!).

By Arun Iyer on Sunday, July 29, 2001 - 07:25 pm:

BRAD,
Can you find any more information on that equation by Ramanujam?
I will give it a full try from my side!!

love arun

By David Loeffler on Sunday, July 29, 2001 - 10:04 pm:

Warning: it's really, really hard to prove!
(He also showed that u7n+5=7k, and u11n+6=11k). The proofs of the results for 5 and 7 are given by Hardy and Wright in their book "An introduction to the theory of numbers". There is also a proof in American Mathematical Monthly June 1999 issue, which can be found on the web at www.maths.unsw.edu.au/~mikeh/webpapers/paper60.pdf,
but I will freely confess that I don't understand a word of it! (It uses lots of weird results that presumably one is supposed to already know, involving "Jacobi's triple product identity" etc.

See what you make of it!

David