A057716 The nonpowers of 2.

0, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74

Offset: 0

Author

John Lindgren (john.lindgren(AT)Eng.Sun.COM), Oct 24 2000

Keywords

• nonn
• easy

Comments

a(n) is the length signature of a string plus its length.

The positive members of this sequence are exactly the numbers that can be expressed as the sum of two or more consecutive positive integers (cf. A138591). - David Wasserman, Jan 24 2002

Starting at 3, these are the positions of the data bits in the single-error-correcting Hamming code.

Except for the offset 0, sequence corresponds to numbers with at least an odd divisor > 1 (For largest odd divisor see A000265). - Lekraj Beedassy, Apr 12 2005

These are exactly the numbers n with the property that, given the n(n-1)/2 sums of pairs, the original numbers can be recovered uniquely. [Nick Reingold, see Winkler reference.]

Subsequence of A158581; A000120(a(n)) > 1. - Reinhard Zumkeller, Apr 16 2009

Range of A140977. - Reinhard Zumkeller, Aug 15 2010

A209229(a(n)) = 0. - Reinhard Zumkeller, Mar 07 2012

A001227(a(n)) > 1. - Reinhard Zumkeller, May 01 2012

Numbers that can be expressed as the sum of at least two consecutive integers; numbers that can be expressed as the difference of two nonconsecutive triangular numbers. - Charles R Greathouse IV, Jul 27 2012

Except for the 1st term 0, these are the integers k such that 2*(2*k-1) divides binomial(2*k-1,k). See Ihringer & Kupavskii. - Michel Marcus, Oct 02 2017

References

• Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
• Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 67-69.
• P. Winkler, Mathematical Mind-Benders, Peters, Wellesley, MA, 2007; see p. 27.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• C. Ballantine and M. Merca, Padovan numbers as sums over partitions into odd parts, Journal of Inequalities and Applications, (2016) 2016:1; doi.
• Carlton Gamer, David W. Roeder, and John J. Watkins, Trapezoidal numbers, Mathematics Magazine 58:2 (1985), pp. 108-110.
• Ferdinand Ihringer and Andrey Kupavskii, Regular Intersecting Families, arXiv:1709.10462 [math.CO], 2017. See Lemma 24 p. 11.
• M. A. Nyblom, On the representation of the integers as a difference of nonconsecutive triangular numbers, Fibonacci Quarterly 39:3 (2001), pp. 256-263.
• Henri Picciotto, Staircases.
• J. M. Rodriguez Caballero, A characterization of the hypotenuses of primitive pythagorean triangles using partitions into consecutive parts, Amer. Math. Monthly 126 (2019), 74-77.

Crossrefs

Complement of A000079. Cf. A057717, A001227, A103586, A138591, A138592.

See A074894 for more about the question of when the sums of n numbers taken k at a time determine the numbers.

Programs

Haskell

a057716 n = a057716_list !! n
a057716_list = filter ((== 0) . a209229) [0..]
-- Reinhard Zumkeller, Mar 07 2012

Maple

select(t -> t/2^padic:-ordp(t,2) <> 1, [$0..100]); # Robert Israel, May 05 2015

Mathematica

Module[{nn = 100,maxpwr},maxpwr = Floor[Log[2, nn]]; Complement[Range[0, nn], 2^Range[0, maxpwr]]]  (* Harvey P. Dale, May 24 2012 *)
Complement[Range[0, 99], 2^Range[0, 7]] (* Alonso del Arte, May 05 2015 *)

PARI

print1(0);for(n=1,5,for(m=2^n+1,2^(n+1)-1,print1(", "m))) \\ Charles R Greathouse IV, Mar 07 2012

Python

def A057716(n): return n + (n + n.bit_length()).bit_length() # Matthew Andres Moreno, Jun 16 2024

Python

from itertools import count, islice
def agen(): # generator of terms
    yield 0
    yield from (j for i in count(0) for j in range(2**i+1, 2**(i+1)))
print(list(islice(agen(), 70))) # Michael S. Branicky, Oct 11 2024

Formula

a(n) = n + [log_2(n + [log_2(n)])] gives this sequence with the exception of a(1) = 1. - David W. Wilson, Mar 29 2005

Find k such that 2^k - (k + 1) <= n < 2^(k+1) - (k + 2), then a(n) = n + k + 1.

Numbers n = 2a(k) - 1, k > 0 are such that Sum_{k=0..n} B_k*M(n-k)*binomial(n, k) = 0 where B_k is the k-th Bernoulli number and M_k the k-th Motzkin number. - Benoit Cloitre, Oct 19 2005

From Robert Israel, May 05 2015: (Start)

G.f.: (1-x)^(-2)*Sum(m>=0, x^(2^m-m)*(2^m*x-2^m*x^2+x) + x^(2^(m+1)-m)*(2^(m+1)*x-2^(m+1)-x)).

a(i-m) = i for 2^m < i < 2^(m+1).

a(n) = A103586(n) + n for n >= 1. (End)

Extensions

Better description from Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 2001