Interesting. Is it then true that there is a prime of every length when expressed in the binary system? Then I suppose we could always choose the smallest such for each length, and we would never need more than ~log_2(n) such numbers in the representation. So this representation is as compact as the usual binary system? At 01:08 PM 7/10/2006, Michael Reid wrote:
In an analogy with Zeckendorf (Fibonacci) number systems, can every positive integer be expressed as a _sum_ of _distinct_ (positive) primes ?
If not, what is the smallest integer not so expressible?
For this purpose, I'll allow "1" as a "prime", although I suspect it's only needed a constant number of times.
yes, with your convention of considering 1 to be prime. you've already shown how to do the first few cases. for a larger value of N , let p be the largest prime <= N . then p > N/2 , by the theorem usually called "Bertrand's postulate". express N - p as a sum of distinct "primes", and add p to the result. since p > N - p , the primes in this sum are distinct.
it is probably easy to modify this argument to show that 1 is only needed a few times (twice?)
mike