A187279 a(n) is the least number of terms needed to represent n as a sum of powers of the same prime.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 3, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 3, 1, 2, 3, 2, 3, 2, 1, 2, 1, 2, 3, 1, 2, 2, 1, 2, 3, 3, 1, 2, 1, 2, 3, 3, 4, 4, 1, 2, 1, 2, 1, 2, 3, 2, 3, 3, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 3, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2

Offset: 1

Author

David Wasserman, Mar 07 2011

Keywords

• nonn
• easy

Comments

A000961 gives all n such that a(n)=1. A024619 gives all n such that a(n) > 1.

If a(n) < m, let p be a prime such that n is a sum of < m powers of p. Then for any positive integers c_1, ... c_m that add up to n, p divides the m-nomial coefficient n!/(c_1!*c_2!*...*c_m!). If a(n) >= m then there is no prime that divides all such coefficients.

Examples

			a(15) = 3 because 15 can be expressed with powers of 3 as 3^2+3^1+3^1, or with powers of 7 as 7^1+7^1+7^0, or with powers of 13 as 13^1+13^0+13^0, but there is no such expression with fewer than three terms.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Mathematics StackExchange, The largest number y in which (x!)^(x+y)|(x^2)!

Programs

Maple

with(numtheory):
b:= proc(n, p) local c, m; m:=n; c:=0;
      while m>0 do c:= c+irem(m, p, 'm') od; c
    end:
a:= n-> min(seq(b(n, ithprime(i)), i=1..pi(n+1))):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 06 2013

Mathematica

Join[{1}, Table[Min[Plus @@@ IntegerDigits[n, Prime[Range[PrimePi[n]]]]], {n, 2, 110}]] (* T. D. Noe, Mar 08 2011 *)