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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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 December 19 23:11 EST 2014. Contains 252240 sequences.