login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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]

LINKS

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

FORMULA

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]

EXAMPLE

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

MAPLE

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

PROG

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

(PARI)

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

(PARI)

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)

CROSSREFS

Cf. A006519, A080468.

Sequence in context: A246960 A192099 A193101 * A088696 A004738 A043554

Adjacent sequences:  A100658 A100659 A100660 * A100662 A100663 A100664

KEYWORD

easy,nonn

AUTHOR

David Wasserman, Jan 14 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 31 21:39 EDT 2014. Contains 248871 sequences.