A078607 -id:A078607 - cp's OEIS frontend

A230748 Duplicate of A078607.

2, 3, 4, 6, 7, 9, 10, 12, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 42, 43, 45, 46, 48, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 63, 65, 66, 68, 69, 71, 72, 74, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 89, 91, 92

Offset: 1

dead

Original definition: a(n) = floor(1/(1-x)) where x^n = 1/2.

A030052 Smallest number whose n-th power is a sum of distinct smaller positive n-th powers.

Original entry on oeis.org

3, 5, 6, 15, 12, 25, 40, 84, 47, 63, 68, 81, 102, 95, 104, 162, 123

Offset: 1

Richard C. Schroeppel

Sprague has shown that for any n, all sufficiently large integers are the sum of distinct n-th powers. Sequence A001661 lists the largest number not of this form, so we know that a(n) is less than or equal to the next larger n-th power. - M. F. Hasler, May 25 2020

a(18) <= 200, a(19) <= 234, a(20) <= 242; for more upper bounds see the Al Zimmermann's Programming Contests link: The "Final Report" gives exact solutions for n = 16 through 30; those for n = 16 and 17 have been confirmed to be minimal by Jeremy Sawicki. - M. F. Hasler, Jul 20 2020

			3^1 = 2^1 + 1^1, and there is no smaller solution given that the r.h.s. is the smallest possible sum of distinct positive powers.
For n = 2, one sees immediately that 3 is not a solution (3^2 > 2^2 + 1^2) and one can check that 4^2 isn't equal to Sum_{x in A} x^2 for any subset A of {1, 2, 3}. Therefore, the well known hypotenuse number 5 (cf. A009003) with 5^2 = 4^2 + 3^2 provides the smallest possible solution.
a(17) = 123 since 123^17 = Sum {3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 30, 33, 34, 35, 38, 40, 41, 43, 51, 52, 54, 55, 58, 59, 60, 63, 66, 69, 70, 71, 72, 73, 75, 76, 81, 86, 87, 88, 89, 90, 92, 95, 98, 106, 107, 108, 120}^17, with obvious notation. [Solution found by Jeremy Sawicki on July 3, 2020, see Al Zimmermann's Programming Contests link.] - _M. F. Hasler_, Jul 18 2020
For more examples, see the link.

R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948) 466-468.
Various authors, How each power is decomposed
Eric Weisstein's World of Mathematics, Diophantine Equation.
Al Zimmermann, Sum Of Powers: Final Report, Al Zimmermann's Programming Contests, April-July 2020

Cf. A078607, A332065, A332097, A332101.

Other sequences defined by sums of distinct n-th powers: A001661, A364637.

A030052(n, m=n\/log(2)+1, s=0)={if(!s, until(A030052(n, m, (m+=1)^n),), s < 2^n || s > (m+n+1)*m^n\(n+1), m=s<2, m=min(sqrtnint(s, n), m); s==m^n || until( A030052(n, m-1, s-m^n) || (s>=(m+n)*(m-=1)^n\(n+1) && !m=0), )); m} \\ Does exhaustive search to find the least solution m. Use optional 2nd arg to specify a starting value for m. Calls itself with nonzero 3rd (optional) argument: in this case, returns nonzero iff s is the sum of powers <= m^n. - For illustration only: takes very long already for n = 8 and n >= 10. - M. F. Hasler, May 25 2020

a(n) <= A001661(n)^(1/n) + 1. - M. F. Hasler, May 25 2020

a(n) >= A332101(n) = A078607(n)+2 (conjectured). - M. F. Hasler, May 25 2020

a(8)-a(10) found by David W. Wilson
a(11) from Al Zimmermann, Apr 07 2004
a(12) from Al Zimmermann, Apr 13 2004
a(13) from Manol Iliev, Jan 04 2010
a(14) and a(15) from Manol Iliev, Apr 28 2011
a(16) and a(17) due to Jeremy Sawicki, added by M. F. Hasler, Jul 20 2020

A332101 Least m such that m^n <= Sum_{k

Original entry on oeis.org

2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 42, 44, 45, 47, 48, 50, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 78, 80, 81, 83, 84, 86, 87, 89, 90, 91, 93, 94, 96, 97

Offset: 0

M. F. Hasler, Apr 14 2020

nonn

In a list (1^n, 2^n, 3^n, ...) (rows of table A051128 or A051129), a(n) is the index of the first term less than or equal to the sum of all earlier terms, cf. example.

Obviously a lower bound for any s solution to s^n = Sum_{x in S} x^n, S subset of {1, ..., s-1}, cf. A030052.

			For n = 0, m^0 > Sum_{0 < k < m} k^0 = 0 for m = 0, 1 (empty sums), but 2^0 = Sum_{0 < k < 2} k^0 = 1, so a(0) = 2.
For n = 1, 1^1 > Sum_{0 < k < 1} k^1 = 0 (empty sum) and 2^1 > Sum_{0 < k < 2} k^1 = 1, but 3^1 <= Sum_{0 < k < 3} k^1 = 1 + 2, so a(1) = 3.
To find a(n) one can add up terms in row n of the table k^n until the sum equals or exceeds the next term, whose column number k is then a(n):
  n |k: 1  2   3   4    5    6          Comment
  --+---------------------------------------------------------------
  1 |  1   2   3                  1 < 2 but 1 + 2 >= 3, so a(1) = 3.
  2 |  1   4   9  16   25         1 + 4 + 9 + 16 > 25, and a(2) = 5.
  3 |  1   8  27  64  125  216    1 + 8 + 27 + 64 + 125 > 216: a(3) = 6.

Michael De Vlieger, Table of n, a(n) for n = 0..1000
Brennan Benfield and Oliver Lippard, Integers that are not the sum of positive powers, arXiv:2404.08193 [math.NT], 2024.

Cf. A051128, A051129.

Cf. A078607, A332097 (maximum of E(s), cf comments), A030052 (least k such that k^n = sum of distinct n-th powers), A332065 (all k such that k^n is a sum of distinct n-th powers).

Table[Block[{m = 1, s = 0}, While[m^n > s, s = s + m^n; m++]; m], {n, 0, 66}] (* Michael De Vlieger, Apr 30 2020 *)

PARI
```
apply( A332101(n,s)=for(m=1,oo, s
				
```

a(n) = round(n / log(2)) + 2. (Conjectured; verified up to 10^4, in particular for 3525/log(2) = 5085.500019... and 7844/log(2) ~ 11316.49990...)

a(n) = A078607(n) + 2 for almost all n > 1. (n = 777451915729368 might be an exception to this equality or the above one.) - M. F. Hasler, May 08 2020

A078608 a(n) = ceiling(2/(2^(1/n)-1)).

Original entry on oeis.org

2, 5, 8, 11, 14, 17, 20, 23, 25, 28, 31, 34, 37, 40, 43, 46, 49, 51, 54, 57, 60, 63, 66, 69, 72, 75, 77, 80, 83, 86, 89, 92, 95, 98, 100, 103, 106, 109, 112, 115, 118, 121, 124, 126, 129, 132, 135, 138, 141, 144, 147, 150, 152, 155, 158, 161, 164, 167, 170, 173, 176, 178, 181

Offset: 1

Jon Perry, Dec 09 2002

nonn

For n >= 2, a(n) is the least positive integer x such that 2*x^n > (x+2)^n. For example, a(2)=5 as 4^2=16, 5^2=25, 6^2=36 and 7^2=49.
Coincides with floor( 2*n/(log 2) ) for all n from 1 to 777451915729367 but differs at 777451915729368. See A129935.
The first few values of n for which this sequence differs from floor( 2*n/(log 2) ) were found by Dean Hickerson in 2002. - N. J. A. Sloane, Apr 30 2014
The sequence floor( log(n)/(2*log(2)) ) is mentioned by Erdős and Selfridge (1973). This sequence begins 0,0,0,1,1,1,1,... = 0 (3 times), 1 (12 times), 2 (48 times), 3 (192 times), 4 (768 times), ..., and grows too slowly to have its own entry. It is related to the game studied by Hales and Jewett (1963). - N. J. A. Sloane, Dec 02 2016

S. Golomb, "Martin Gardner and Tictacktoe," in Demaine, Demaine, and Rodgers, eds., A Lifetime of Puzzles, A K Peters, 2008, pp. 293-301.
S. W. Golomb and A. W. Hales, "Hypercube Tic-Tac-Toe", in "More Games of No Chance", ed. R. J. Nowakowski, MSRI Publications 42, Cambridge University Press, 2002, pp. 167-182. Here it is stated that the first counterexample is at n=6847196937, an error due to faulty multiprecision arithmetic. The correct value was found by Dean Hickerson in 2002, and J. Buhler in 2004, and is reported in S. Golomb (2008).
Dean Hickerson, Email to Jon Perry and N. J. A. Sloane, Dec 16 2002. Gives first three terms of A129935: 777451915729368, 140894092055857794, 1526223088619171207, as well as five later terms. - N. J. A. Sloane, Apr 30 2014

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Max Alekseyev and others, Integer Parts [in Russian]
Max Alekseyev and others, Integer Parts [in Russian] [Cached copy in pdf format]
Art of Problem Solving, Logarithmic identity
Paul Erdős and John L. Selfridge, On a combinatorial game, Journal of Combinatorial Theory, Series A 14.3 (1973): 298-301.
S. W. Golomb and A. W. Hales, Hypercube Tic-Tac-Toe
A. W. Hales and R. I. Jewett, Regularity and Positional Games, Transactions of the American Mathematical Society, vol. 106, no. 2, Feb. 1963, 222-229.
K. O'Bryant, The sequence of fractional parts of roots, arXiv preprint arXiv:1410.2927 [math.NT], 2014-2015.
Index entries for sequences which agree for a long time but are different

Cf. A078607, A078609, A129935.

a078608 = ceiling . (2 /) . (subtract 1) . (2 **) . recip . fromIntegral
-- Reinhard Zumkeller, Mar 27 2015

Table[(Ceiling[2/(2^(1/n)-1)]), {n, 1, 100}] (* Vincenzo Librandi, May 01 2014 *)

for (n=2,50, x=2; while (2*x^n<=((x+2)^n),x++); print1(x","))

Edited by Dean Hickerson, Dec 17 2002

Revised by N. J. A. Sloane, Jun 07 2007

A332097 Maximum of s^n - Sum_{0 < x < s} x^n.

Original entry on oeis.org

1, 1, 4, 28, 317, 4606, 84477, 1919575, 47891482, 1512466345, 48627032377, 1930020260416, 77986967769593, 3624337209819538, 178110510699972510, 9381158756438306167, 548676565488760277878, 31900481466759651567625, 2189463436999785648552851, 144075114432622269076465962

Offset: 0

M. F. Hasler, May 07 2020

nonn

For small values of s, we have Sum_{0 < x < s} x^n ~ (s-1)^n, but for s > n/log(2) + 1.5 (cf. A332101) the difference E(s) = s^n - Sum_{0 < x < s} x^n becomes negative. Just before, the difference has its maximum: We have E(s) < E(s+1) <=> 2*s^n < (s+1)^n <=> s < 1/(2^(1/n)-1), so E takes its maximum at s = A078607(n), the least integer larger than this limiting value. This appears to be almost always equal to A332101(n) - 2.

Alois P. Heinz, Table of n, a(n) for n = 0..367

Cf. A030052 (least k such that k^n = sum of distinct n-th powers).
Cf. A078607 (s for which E(s) = a(n) <=> least k such that 2*k^n > (k+1)^n).
Cf. A332065 (all k such that k^n is a sum of distinct n-th powers).
Cf. A332101 (least k such that k^n <= sum of all smaller n-th powers).

a:= proc(n) option remember; `if`(n=0, 1, (s->
      s^n-add(x^n, x=1..s-1))(ceil(1/(2^(1/n)-1))))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, May 09 2020

a[0] = 1; a[n_] := (s = Ceiling[1/(2^(1/n) - 1)])^n - Sum[k^n, {k, 1, s - 1}]; Array[a, 20, 0] (* Amiram Eldar, May 09 2020 *)

{apply( A332097(n,s=1\(sqrtn(2,n-!n)-1))=(s+1)^n-sum(k=1,s,k^n), [0..20])}

a(n) = s^n - Sum_{0 < x < s} x^n for s = ceiling(1/(2^(1/n)-1)) = A078607(n).

A224996 a(n) = floor(1/f(x^(1/n))) for x = 2, where f computes the fractional part.

Original entry on oeis.org

2, 3, 5, 6, 8, 9, 11, 12, 13, 15, 16, 18, 19, 21, 22, 24, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 39, 41, 42, 44, 45, 47, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 75, 77, 78, 80, 81, 83, 84, 86, 87, 88, 90, 91, 93, 94, 96, 97

Offset: 2

T. D. Noe, Apr 26 2013

First denominator of continued fraction representing 2^(1/n): [1,a(n),....] so that 1+1/a(n) is first convergent for 2^(1/n). - Carmine Suriano, Apr 29 2014

a(n) is the largest integer y that satisfies (y+1)^n - y^n >= y^n, or equivalently (y+1)^n >= 2*y^n. - Charles Kusniec, Jan 19 2025

Melvyn B. Nathanson, On the fractional parts of roots of positive real numbers, Amer. Math. Monthly, 120 (2013), 409-429.

Cf. A224995, A224997, A224998, A001651, A047211, A047203, A047290, A047332.

Cf. A078607 (the smallest integer y that satisfies (y+1)^n - y^n < y^n).

th = 2; t = Table[Floor[1/FractionalPart[th^(1/n)]], {n, 2, 100}]

a(n) = floor(n/log(2)-1/2). - Andrey Zabolotskiy, Dec 01 2017

A078609 Least positive integer x such that 2*x^n>(x+3)^n.

Original entry on oeis.org

8, 12, 16, 21, 25, 29, 34, 38, 42, 47, 51, 55, 60, 64, 68, 73, 77, 81, 86, 90, 94, 99, 103, 107, 112, 116, 120, 125, 129, 133, 138, 142, 146, 150, 155, 159, 163, 168, 172, 176, 181, 185, 189, 194, 198, 202, 207, 211, 215, 220, 224, 228, 233, 237, 241, 246, 250

Offset: 2

Jon Perry, Dec 09 2002

nonn

			a(2)=8 as 7^2=49, 8^2=64, 10^2=100 and 11^2=121.

Cf. A078607, A078608.

for (n=2,50, x=2; while (2*x^n<=((x+3)^n),x++); print1(x","))

a(n) = ceiling(3/(2^(1/n)-1)). For most n, a(n) = floor(3n/log(2)-1/2), but there are exceptions, starting with n=32 and n=52113.

Edited by Dean Hickerson, Dec 17 2002

A332096 Irregular table where T(n,m) = min_{A subset {1..m-1}} |m^n - Sum_{x in A} x^n|, for 1 <= m <= A332098(n) = largest m for which this is nonzero.

Original entry on oeis.org

1, 1, 1, 3, 4, 2, 0, 1, 0, 1, 1, 7, 18, 28, 25, 0, 1, 8, 0, 7, 1, 1, 15, 64, 158, 271, 317, 126, 45, 17, 59, 14, 2, 15, 3, 0, 2, 1, 2, 1, 2, 2, 2, 1, 2, 0, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 31, 210, 748, 1825, 3351, 4606, 3760, 398, 131, 299, 0, 318, 0, 8

Offset: 1

M. F. Hasler, Jul 20 2020

nonn

It is known (Sprague 1948, cf. A001661) that for any n, only a finite number of positive integers are not the sum of distinct positive n-th powers. Therefore each row is finite, their lengths are given by A332098.
The number of nonzero terms in row n is A332066(n).
The column of the first zero (exact solution m^n = Sum_{x in A} x^n) in each row is given by A030052, unless A030052(n) = A332066(n) + 1 = A332098(n) + 1.

			The table reads:
  n\ m=1   2    3    4     5     6     7     8    9   10   11  12   13
----+--------------------------------------------------------------------------
  1 |  1   1                                                  (A332098(1) = 2.)
  2 |  1   3    4    2     0     1     0     1                (A332098(2) = 8.)
  3 |  1   7   18   28    25     0     1     8    0    7    1
  4 |  1  15   64  158   271   317   126    45   17   59   14   2   15  3  0 ...
  5 |  1  31  210  748  1825  3351  4606  3760  398  131  299   0  318  0  8 ...
The first column is all ones (A000012), since {1..m-1} = {} for m = 1.
The second column is 2^n - 1 = A000225 \ {0}, since {1..m-1} = {1} for m = 2.
The third column is 3^n - 2^n - 1 = |A083321(n)| for n > 1.

R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51 (1948) 466-468.

Cf. A001661, A332098, A332066, A030052, A332097, A078607.

Cf. A000012, A000225, A083321.

A332096(n,m,r=0)={if(r, (m<2||r<2^(n-1)) && return(r-1); my(E, t=1); while(m^n>=r, E=m--); E=abs(r-(m+!!E)^n); for(a=2,m, if(r=m && return(min(E,r-t)); while(m>=t && E, E=min(self()(n,m-1,r-m^n),E); E && E=min(self()(n,m-=1,r),E)); E, m < n/log(2)+1.5, m^n-sum(x=1,m-1,x^n), self()(n,m-1,m^n))}

For all n and m, T(n,m) <= A332097(n) = T(n,m*) with m* = A078607(n).

For m <= m* + 1, T(n,m) = m^n - Sum_{0 < x < m} x^n.

A110882 a(n) is the least integer x such that x^n < 2 * (x-1)^n.

Original entry on oeis.org

1, 3, 4, 5, 7, 8, 10, 11, 13, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 28, 30, 31, 33, 34, 36, 37, 39, 40, 41, 43, 44, 46, 47, 49, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 64, 66, 67, 69, 70, 72, 73, 75, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 90, 92, 93, 95, 96, 98, 99, 101, 102

Offset: 0

Ken Tozier (kentozier(AT)comcast.net), Oct 02 2005

nonn

Similar to the Beatty sequence for 1/log(2).

			a(9) = 14 because 14^9 < 2 * 13^9.

Equals A078607(n)+1 for n > 0.

{1}~Join~Table[SelectFirst[Range[10^3], #^n < 2 (# - 1)^n &], {n, 70}] (* Michael De Vlieger, May 01 2016, Version 10 *)

Edited by Don Reble, May 16 2006

cp's OEIS Frontend

A230748 Duplicate of A078607.

Views

Author

Keywords

Comments

A030052 Smallest number whose n-th power is a sum of distinct smaller positive n-th powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A332101 Least m such that m^n <= Sum_{k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A078608 a(n) = ceiling(2/(2^(1/n)-1)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A332097 Maximum of s^n - Sum_{0 < x < s} x^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A224996 a(n) = floor(1/f(x^(1/n))) for x = 2, where f computes the fractional part.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A078609 Least positive integer x such that 2*x^n>(x+3)^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A332096 Irregular table where T(n,m) = min_{A subset {1..m-1}} |m^n - Sum_{x in A} x^n|, for 1 <= m <= A332098(n) = largest m for which this is nonzero.

Views

Author

Keywords

Comments