A080468 -id:A080468 - cp's OEIS frontend

A055938 Integers not generated by b(n) = b(floor(n/2)) + n (complement of A005187).

2, 5, 6, 9, 12, 13, 14, 17, 20, 21, 24, 27, 28, 29, 30, 33, 36, 37, 40, 43, 44, 45, 48, 51, 52, 55, 58, 59, 60, 61, 62, 65, 68, 69, 72, 75, 76, 77, 80, 83, 84, 87, 90, 91, 92, 93, 96, 99, 100, 103, 106, 107, 108, 111, 114, 115, 118, 121, 122, 123, 124, 125, 126, 129

Offset: 1

Alford Arnold, Jul 21 2000

Note that the lengths of the consecutive runs in a(n) form sequence A001511.
Integers that are not a sum of distinct integers of the form 2^k-1. - Vladeta Jovovic, Jan 24 2003
Also n! never ends in this many 0's in base 2 - Carl R. White, Jan 21 2008
A079559(a(n)) = 0. - Reinhard Zumkeller, Mar 18 2009
These numbers are dead-end points when trying to apply the iterated process depicted in A071542 in reverse, i.e. these are positive integers i such that there does not exist k with A000120(i+k)=k. See also comments at A179016. - Antti Karttunen, Oct 26 2012
Conjecture: a(n)=b(n) defined as b(1)=2, for n>1, b(n+1)=b(n)+1 if n is already in the sequence, b(n+1)=b(n)+3 otherwise. If so, then see Cloitre comment in A080578. - Ralf Stephan, Dec 27 2013
Numbers n for which A257265(m) = 0. - Reinhard Zumkeller, May 06 2015. Typo corrected by Antti Karttunen, Aug 08 2015
Numbers which have a 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 28 2025

			Since A005187 begins 0 1 3 4 7 8 10 11 15 16 18 19 22 23 25 26 31... this sequence begins 2 5 6 9 12 13 14 17 20 21

Complement of A005187. Setwise difference of A213713 and A213717.
Row 1 of arrays A257264, A256997 and also of A255557 (when prepended with 1). Equally: column 1 of A256995 and A255555.
Cf. also arrays A254105, A254107 and permutations A233276, A233278.
Left inverses: A234017, A256992.
Cf. A001511, A046699, A079559, A080578, A086343, A227359, A227408, A234016.
Gives positions of zeros in A213714, A213723, A213724, A213731, A257265, positions of ones in A213725-A213727 and A256989, positions of nonzeros in A254110.
Cf. also A010061 (integers that are not a sum of distinct integers of the form 2^k+1).
Analogous sequence for factorial base number system: A219658, for Fibonacci number system: A219638, for base-3: A096346. Cf. also A136767-A136774.
Cf. A257508, A257509, A257126.

a055938 n = a055938_list !! (n-1)
a055938_list = concat $
   zipWith (\u v -> [u+1..v-1]) a005187_list $ tail a005187_list
-- Reinhard Zumkeller, Nov 07 2011

a[0] = 0; a[1] = 1; a[n_Integer] := a[Floor[n/2]] + n; b = {}; Do[ b = Append[b, a[n]], {n, 0, 105}]; c =Table[n, {n, 0, 200}]; Complement[c, b]
(* Second program: *)
t = Table[IntegerExponent[(2n)!, 2], {n, 0, 100}]; Complement[Range[t // Last], t] (* Jean-François Alcover, Nov 15 2016 *)

L=listcreate();for(n=1,1000,for(k=2*n-hammingweight(n)+1,2*n+1-hammingweight(n+1),listput(L,k)));Vec(L) \\ Ralf Stephan, Dec 27 2013

def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
def a079559(n): return 1 if n==0 else a043545(n + 1)*a079559(n + 1 - a053644(n + 1))
print([n for n in range(1, 201) if a079559(n)==0]) # Indranil Ghosh, Jun 11 2017, after the comment by Reinhard Zumkeller

;; utilizing COMPLEMENT-macro from Antti Karttunen's IntSeq-library)
(define A055938 (COMPLEMENT 1 A005187))
;; Antti Karttunen, Aug 08 2015

a(n) = A080578(n+1) - 2 = A080468(n+1) + 2*n (conjectured). - Ralf Stephan, Dec 27 2013
From Antti Karttunen, Aug 08 2015: (Start)
Other identities. For all n >= 1:
A234017(a(n)) = n.
A256992(a(n)) = n.
A257126(n) = a(n) - A005187(n).
(End)

More terms from Robert G. Wilson v, Jul 24 2000

A080578 a(1)=1; for n > 1, a(n) = a(n-1) + 1 if n is already in the sequence, a(n) = a(n-1) + 3 otherwise.

Original entry on oeis.org

1, 4, 7, 8, 11, 14, 15, 16, 19, 22, 23, 26, 29, 30, 31, 32, 35, 38, 39, 42, 45, 46, 47, 50, 53, 54, 57, 60, 61, 62, 63, 64, 67, 70, 71, 74, 77, 78, 79, 82, 85, 86, 89, 92, 93, 94, 95, 98, 101, 102, 105, 108, 109, 110, 113, 116, 117, 120, 123, 124, 125, 126

Offset: 1

N. J. A. Sloane and Benoit Cloitre, Mar 23 2003

nonn

More generally for fixed r, there is a nice connection between the sequence a(1)=1, a(n) = a(n-1) + 1 if n is in the sequence, a(n) = a(n-1) + r + 1 otherwise and the so-called metafibonacci sequences. Indeed, (a(n)-n)/r is a generalized metafibonacci sequence of order r as defined in Ruskey's recent paper (reference given at A046699). - Benoit Cloitre, Feb 04 2007

In the Fokkink-Joshi paper, this sequence is the Cloitre (0,1,1,3)-hiccup sequence. - Michael De Vlieger, Jul 29 2025

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Robbert Fokkink and Gandhar Joshi, On Cloitre's hiccup sequences, arXiv:2507.16956 [math.CO], 2025. See pp. 3, 5, 11.

Cf. A080455, A080456, A080457, A080458, A080036, A080037, A080468.

a080578 n = a080578_list !! (n-1)
a080578_list = 1 : f 2 [1] where
   f x zs@(z:_) = y : f (x + 1) (y : zs) where
     y = if x `elem` zs then z + 1 else z + 3
-- Reinhard Zumkeller, Sep 26 2014

l={1}; a=1; For[n=2, n<=100, If[MemberQ[l, n], a=a+1, a=a+3]; AppendTo[l, a]; n++]; l (* Indranil Ghosh, Apr 07 2017 *)

a(n)=if(n<2,1,a(n+1-2^floor(log(n)/log(2)))+2*2^floor(log(n)/log(2))-1) \\ Benoit Cloitre, Feb 04 2007

l=[1]
a=1
for n in range(2, 101):
    a += 3 if n not in l else 1
    l.append(a)
print(l) # Indranil Ghosh, Apr 07 2017

a(n) = 2n + O(1); a(2^n) = 2^(n+1). - Benoit Cloitre, Oct 12 2003
a(1) = 1, for n >= 2 a(n) = a(n + 1 - 2^floor(log(n)/log(2))) + 2*2^floor(log(n)/log(2)) - 1; (a(n) - n)/2 = A046699(n) for n >= 2. - Benoit Cloitre, Feb 04 2007
a(n) = A055938(n-1) + 2 (conjectured). - Ralf Stephan, Dec 27 2013

A233270 a(n) = A233271(n) - A179016(n).

Original entry on oeis.org

0, 0, -1, 0, 0, 0, 1, 0, 0, 2, 1, 2, 0, 0, 3, 3, 4, 3, 4, 3, 3, 0, 0, 4, 4, 5, 4, 6, 5, 5, 3, 5, 5, 6, 4, 5, 4, 4, 0, 0, 5, 8, 9, 10, 13, 13, 15, 16, 17, 18, 18, 17, 17, 19, 19, 17, 17, 18, 18, 17, 16, 15, 13, 13, 10, 9, 8, 5, 0, 0, 6, 9, 14, 17, 18, 20, 22, 21

Offset: 0

Antti Karttunen, Dec 14 2013

For all n>=2, a(1+A213710(n)) = n-2.
Except for a(2)=-1 (which seems to be the only negative term in the sequence), the sequences A218600 and A213710 give the positions of zeros.
Furthermore, each subrange [A213710(n)..A218600(n+1)] is palindromic. A233268 gives the middle points of those ranges, the sequence A234018 gives the values at those points, while A234019 gives the maximum term in that range in this sequence.

			This irregular table begins as:
0;
0;
-1;
0, 0;
0, 1, 0;
0, 2, 1, 2, 0;
0, 3, 3, 4, 3, 4, 3, 3, 0;
0, 4, 4, 5, 4, 6, 5, 5, 3, 5, 5, 6, 4, 5, 4, 4, 0;
...
After zero, each row n is A213709(n-1) elements long.

Antti Karttunen, Rows 0..16, flattened

Except for a(2)=-1 (which seems to be the only negative term in the sequence), the sequences A218600 and A213710 give the positions of zeros.

Cf. A080468, A179016, A233271, A233268, A233274, A234018, A234019, A234020.

(define (A233270 n) (- (A233271 n) (A179016 n)))

a(n) = A233271(n) - A179016(n).

a(A218602(n)) = a(n). [This is just a claim that each row is palindrome]

A100661 Quet transform of A006519 (see A101387 for definition). Also, least k such that n+k has at most k ones in its binary representation.

Original entry on oeis.org

1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5

Offset: 1

David Wasserman, Jan 14 2005

If n+a(n) has exactly a(n) 1's in binary, then a(n+1) = a(n)+1, but if n+a(n) has less than a(n) 1's, then a(n+1) = a(n)-1. a(n) is the number of terms needed to represent n as a sum of numbers of the form 2^k-1. [Jeffrey Shallit]
Is a(n) = A080468(n+1)+1?
Compute a(n) by repeatedly subtracting the largest number 2^k-1<=n until zero is reached. The number of times a term was subtracted gives a(n). Examples: 5 = 3 + 1 + 1 ==> a(5) = 3 6 = 3 + 3 ==> a(6) = 2. Replace all zeros in A079559 by -1, then the a(n) are obtained as cumulative sums (equivalent to the generating function given); see fxtbook link. [Joerg Arndt, Jun 12 2006]

			a(4) = 2 because 4+2 (110) has two 1's, but 4+1 (101) has more than one 1.
Conjecture (Joerg Arndt):
a(n) is the number of bits in the binary words of sequence A108918
......A108918.A108918..n..=..n.=.(sum.of.term.2^k-1)
........00001.1.....00001.=..1.=..1
........00011.2.....00010.=..2.=..1.+.1
........00010.1.....00011.=..3.=..3
........00101.2.....00100.=..4.=..3.+.1
........00111.3.....00101.=..5.=..3.+.1.+.1
........00110.2.....00110.=..6.=..3.+.3
........00100.1.....00111.=..7.=..7
........01001.2.....01000.=..8.=..7.+.1
........01011.3.....01001.=..9.=..7.+.1.+.1
........01010.2.....01010.=.10.=..7.+.3
........01101.3.....01011.=.11.=..7.+.3.+.1
........01111.4.....01100.=.12.=..7.+.3.+.1.+.1
........01110.3.....01101.=.13.=..7.+.3.+.3
........01100.2.....01110.=.14.=..7.+.7
........01000.1.....01111.=.15.=.15

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.3, p. 72.
David Wasserman, Quet transform + PARI code [Cached copy]

Cf. A006519, A080468, A101387, A100808.

Records at indices in (essentially) A000325.

hb:= n-> `if`(n=1, 0, 1+hb(iquo (n, 2))):
a:= proc(n) local m, t;
      m:= n;
      for t from 0 while m>0 do
        m:= m - (2^(hb(m+1))-1)
      od; t
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 22 2011

hb[n_] := If[n==1, 0, 1+hb[Quotient[n, 2]]];
a[n_] := Module[{m=n, t}, For[t=0, m>0, t++, m = m - (2^(hb[m+1])-1)]; t];
Array[a, 100] (* Jean-François Alcover, Oct 31 2020, after Alois P. Heinz *)

A100661(n)=
{ /* method: repeatedly subtract Mersenne numbers */
    local(m, ct);
    if ( n<=1, return(n) );
    m = 1;
    while ( n>m, m<<=1 );
    m -= 1;
    while ( m>n, m>>=1 );
    /* here m=2^k-1 and m<=n */
    ct = 0;
    while ( n, while (m<=n, n-=m; ct+=1);  m>>=1 );
    return( ct );
}
vector(100,n,A100661(n)) /* show terms */
/* Joerg Arndt, Jan 22 2011 */

TInverse(v)=
{
    local(l, w, used, start, x);
    l = length(v); w = vector(l); used = vector(l); start = 1;
    for (i = 1, l,
        while (start <= l && used[start], start++);
        x = start;
        for (j = 2, v[i], x++; while (x <= l && used[x], x++));
        if (x > l,
            return (vector(i - 1, k, w[k]))
            , /* else */
            w[i] = x; used[x] = 1
        )
    );
    return(w);
}
PInverse(v)=
{
    local(l, w);
    l = length(v); w = vector(l);
    for (i = 1, l, if (v[i] <= l, w[v[i]] = i));
    return(w);
}
T(v)=
{
    local(l, w, c);
    l = length(v); w = vector(l);
    for (n = 1, l,
        if (v[n],
            c = 0;
            for (m = 1, n - 1, if (v[m] < v[n], c++));
            w[n] = v[n] - c
            , /* else */
            return (vector(n - 1, i, w[i]))
        )
    );
    return(w);
}
Q(v)=T(PInverse(TInverse(v)));
/* compute terms: */
v = vector(150);
for (n = 1, 150, m = n; x = 1; while (!(m%2), m\=2; x *= 2); v[n] = x); Q(v)

A100661 = lambda n: next(k for k in PositiveIntegers() if (n+k).digits(base=2).count(1) <= k) # D. S. McNeil, Jan 23 2011

a(2^k-1) = 1. For 2^k <= n <= 2^(k+1)-2, a(n) = a(n-2^k+1)+1.

G.f.: x*(2*(1-x)*prod(n>=1, (1+x^(2^n-1))) - 1)/((1-x)^2) = x*(1 + 2*x + 1*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 1*x^6 + 2*x^7 + 3*x^8 + 2*x^9 + ...) [Joerg Arndt, Jun 12 2006]

cp's OEIS Frontend

A055938 Integers not generated by b(n) = b(floor(n/2)) + n (complement of A005187).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Scheme

Formula

Extensions

A080578 a(1)=1; for n > 1, a(n) = a(n-1) + 1 if n is already in the sequence, a(n) = a(n-1) + 3 otherwise.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A233270 a(n) = A233271(n) - A179016(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A100661 Quet transform of A006519 (see A101387 for definition). Also, least k such that n+k has at most k ones in its binary representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A087805 Partial sums of b(k) where {b(k)}{k>=0} = lim{n->oo} {A080578(k)-2k : k=2^n,2^n+1,2^n+2,...}.

Views

Author

Keywords

Crossrefs

Formula