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,6

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.

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)!

Example

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.

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 *)

Crossrefs

Sequence in context: A316555 A337531 A316556 * A076820 A206824 A293810

Adjacent sequences: A187276 A187277 A187278 * A187280 A187281 A187282

Keyword

nonn,easy

Author

David Wasserman, Mar 07 2011

Status

approved