There is an old conjecture that says that the product of consecutive numbers can't be a number to the power of another number (Is there a simple way of saying it???) - except to the power of one (of course).
It was proved by Erdos and Selfrididge in 1975, and it took them 9 years.
To prove that two consecutive numbers can't have that property is easy since gcd(n,n+1)=1 and they can't be to the same power. (except 1 and 2)
Does anybody have the proof?
(I guess it wasn't done using induction...)

Thanks,

Yatir

According to a Google search, it's Erdos and Selfridge: "The product of consecutive integers is never a power",
Illinois Journal of Mathematics 19 (1975), pages 292--301. (Mathematical Reviews 51 #12692). (Aren't search engines wonderful?)
However, I'm not in Cambridge at the moment so I don't have access to a library which which would have the paper. Is anyone on the NRICH team better placed?

David

Thanks for the tip-off David. The proof for general powers is a mountain, but there was a reference for just square powers (Erdos 1939) which I'll indicate the main steps for, to suggest the flavour of such questions. The general ideas involved are within reach of anyone who has taken a first course in number theory, only a few parts need further material. Extra work required in the proof will be indicated by up to 3 (#)s.

1. Aiming for a contradiction, assume there are integers k, m and n > 1 with n(n+1)¼(n+k-1)=m².
2. Write n+i=a_i x_i² where a_i are square-free integers (no square divisors, Erdos writes 'quadratfrei') and if prime p|a_i then p < k (#).
3. Show a_is distinct. (###)
4. Thus a₀ a₁ ¼a_k-1 is greater than the product of the first k square-free integers. i.e. for k > 24 it is greater than (4/3)^k k!. (##)
5. The number of a_i s divisible by prime p < k is equal to or less than [k/p]+1 ([.] denoting integer part) (#).

   Hence
   

   a0 a1 ¼ak-1 <

   Õ p < k

   p[k/p]+1

   
   .

   In fact,
   

   a0 a1 ¼ak-1 < 2k-2

   Õ p < k

   p[k/p]

   
   . (###)

6. But
   

   k! > (2k 3k/2 /6k2 )

   Õ 3 < p < k+1

   p[k/p]

   
   using a theorem of Legendre. (##)
7. Combine inequalities in (4), (5) and (6) to get a contradiction for k > 100. Some other guy (Seimatsu Narumi) had previously established the result for k < 202.

Ian

Ian, Could you please explain stages (4) and (6)...

Thanks,
Yatir

(4) Let S_n= the nth square-free number. It can be verified algebraically that S₁ S₂¼S₂₄ > (4/3)²⁴24!. Thus if we can show S_n > 4n/3, the result holds by induction. This is true as for m > 9, the number of square-free integers equal to or less than m is at most m-[m/4]-1 < 3m/4. (Suffices to omit all the integers divisible by 4.)

(6) Let r_p=the power to which p divides k! for p < k+1 (so that

k!=

Õ p < k+1

pr

). Then for p > 3 use r_p ³ [k/p] and for p=2 and 3 Erdos obtains p^r ³ p^k/(p-1)/kp via Legendre's formula.

This formula states that if k=a₀+a₁p+¼+a_sp^s (0 £ a_i < p) then

rp = (k-

å

ai)/(p-1)

Thus r_p ³ k/(p-1) - (s+1) so put this to the power of p.

Combining the results for p=2, 3 and p > 3 should give the inequality that I wrote down.

The remaining (###) bits are no more complicated than this, just longer. Hope that's okay.

Ian

I'm not sure whether you now understand the first part of (4). All I had meant to indicate was that the a_i s are distinct and square-free so that a_0 ...a_{k-1} is equal to or greater than the product of the k smallest square-free numbers- i.e. the first k such.

Note that I checked none of the arithmetic, rather trusting Erdos. It is necessary by around the 7th step to up k to about 100 anyway.

Tell me if you get anywhere with your factorial idea, I'll dwell on it...

Ian

Yes, I do get (4) now, I thoughtt of a proof and I didn't see that the reasoning was lying right there in front of me...