A023416 -id:A023416 - cp's OEIS frontend

A216431 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A023416.

0, 2, 4, 7, 8, 12, 15, 16, 21, 24, 28, 31, 32, 38, 42, 46, 49, 53, 56, 60, 63, 64, 71, 75, 79, 82, 87, 90, 94, 97, 102, 106, 110, 113, 117, 120, 124, 127, 128, 136, 143, 147, 152, 158, 162, 168, 174, 178, 183, 186, 190, 193, 199, 203, 207, 210, 215, 218, 222

Offset: 0

Alex Ratushnyak, Sep 08 2012

The difference from A233271 stems from the fact that it uses A080791 to count the 0-bits in binary expansion of n, while this sequence uses A023416, which results a slightly different start for the iteration.

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Differs from A233271 only in that this jumps directly from 0 to 2 in the beginning.

Cf. A023416, A010062, A214913, A233271, A233272.

NestList[#+1+DigitCount[#,2,0]&,0,60] (* Harvey P. Dale, Sep 25 2013 *)

a = 0
for n in range(100):
    print(a, end=', ')
    ta = a
    c0 = (a==0)
    while ta>0:
        c0 += 1-(ta&1)
        ta >>= 1
    a += 1 + c0

;; With memoizing definec-macro from Antti Karttunen's IntSeq-library.
(definec (A216431 n) (if (< n 2) (+ n n) (A233272 (A216431 (- n 1)))))
;; Antti Karttunen, Dec 12 2013

If n<2, a(n) = 2n, otherwise, a(n) = A233272(a(n-1)). - Antti Karttunen, Dec 12 2013

Name edited by Antti Karttunen, Dec 12 2013

A334666 For any number with binary expansion (b_1, ..., b_w), replace the i-th "1" by b_i for i = 1..A000120(n) and the j-th "0" by b_{w+1-j} for j = 1..A023416(n); the resulting binary expansion is that of a(n).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 6, 7, 8, 12, 9, 13, 12, 14, 14, 15, 16, 24, 20, 28, 17, 25, 19, 27, 24, 28, 25, 29, 28, 30, 30, 31, 32, 48, 40, 56, 34, 50, 41, 57, 33, 49, 38, 54, 37, 53, 39, 55, 48, 56, 52, 60, 49, 57, 51, 59, 56, 60, 57, 61, 60, 62, 62, 63, 64, 96, 80

Offset: 0

Rémy Sigrist, May 07 2020

Fixed points correspond to A023758.

			For n = 41:
- the binary representation of 41 is "101001",
- the 3 1's are replaced by 1, 0, 1, respectively,
- the 3 0's are replaced by 1, 0, 0, respectively,
- hence we obtain "110001",
- and a(41) = 49.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

See A334667 for a similar sequence.

Cf. A000120, A023416, A023758.

a(n) = { my (b=binary(n), t=vector(#b), l=0, r=#b+1); for (k=1, #b, t[k] = if (b[k], b[l++], b[r--])); fromdigits(t, 2) }

A000120(a(n)) = A000120(n).

A023416(a(n)) = A023416(n).

A100921 n appears A023416(n) times (appearances equal number of 0-bits).

Original entry on oeis.org

0, 2, 4, 4, 5, 6, 8, 8, 8, 9, 9, 10, 10, 11, 12, 12, 13, 14, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 20, 20, 20, 21, 21, 22, 22, 23, 24, 24, 24, 25, 25, 26, 26, 27, 28, 28, 29, 30, 32, 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 36, 36, 36, 36, 37, 37, 37

Offset: 0

Rick L. Shepherd, Nov 21 2004

			The binary representation of 16 is 10000, which has four 0-bits (and one 1-bit), hence 16 appears four times in this sequence (but only once in A100922).

Cf. A100922 (n's appearances equal its number of 1-bits), A030530 (n's appearances equal its total number of bits), A023416, A059009.

Flatten[Table[Table[n, {DigitCount[n, 2, 0]}], {n, 0, 37}]] (* Amiram Eldar, Feb 18 2024 *)

def A059015(n): return 2+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1)
def A100921(n):
    if n == 0: return 0
    m, k = 1, 1
    while A059015(m)<=n: m<<=1
    while m-k>1:
        r = m+k>>1
        if A059015(r)>n:
            m = r
        else:
            k = r
    return m  # Chai Wah Wu, Nov 11 2024

Sum_{n>=1} (-1)^(n+1)/a(n) = Sum_{n>=1} (-1)^(n+1)/A059009(n) = 0.395592509... . - Amiram Eldar, Feb 18 2024

A326280 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)g((1+i)^(A000120(n)-1) (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the real part of f(n).

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 1, 0, 2, 3, 3, 4, 3, 2, 0, -1, 0, 2, 3, 3, 4, 4, 3, 4, 5, 4, 3, 4, 2, 0, -1, -2, -2, -1, 1, 0, 3, 4, 6, 2, 4, 5, 7, 6, 5, 5, 2, 1, 5, 7, 8, 7, 6, 4, 1, 5, 5, 3, 0, 2, -1, -2, -2, -2, -3, -3, -2, -3, -1, 1, 5, -2, 0, 3, 6, 4, 6, 7, 6, 0, 2, 4

Offset: 1

Rémy Sigrist, Jun 22 2019

The idea underlying this sequence is to build an infinite binary tree of Gaussian integers:
- for any n > 0, f(n) has children f(2*n) and f(2*n+1),
- f(n), f(2*n) and f(2*n+1) form a right triangle,
- when u has child v and v has child w, then the angle between the vectors (u,v) and (v,w) is 45 degrees.
Among the first 2^20-1 terms, some values around the origin are missing: -2 - 3*i, -2, i, 2 - 2*i, 2, 4 + i, 5 - 2*i; will they ever appear?
Graphically, f has interesting features (see representations of f in Links section).
This sequence has similarities with A322574.

			See representation of the first layers of the binary tree in links section.

Rémy Sigrist, Table of n, a(n) for n = 1..8191
Rémy Sigrist, Representation of the first layers of the binary tree
Rémy Sigrist, Colored representation of f(n) for n = 1..2^20-1 (where the hue is function of n)
Rémy Sigrist, Colored representation of f(n) for n = 1..2^20-1 (where black pixels correspond to even n)
Rémy Sigrist, Density plot of the first 2^22-1 terms
Rémy Sigrist, PARI program for A326280

See A326281 for the imaginary part of f.

Cf. A000120, A023416, A322574.

PARI
```
See Links section.
```

A326281 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)g((1+i)^(A000120(n)-1) (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the imaginary part of f(n).

Original entry on oeis.org

0, -1, 1, -2, -1, 1, 2, -3, -3, -2, 0, -1, 2, 3, 3, -3, -4, -4, -3, -4, -2, 0, 1, -3, -1, 2, 3, 3, 4, 4, 3, -2, -4, -5, -5, -6, -5, -4, 0, -5, -5, -3, 1, -2, 1, 3, 2, -6, -4, -3, 2, -1, 4, 4, 5, 2, 4, 5, 6, 6, 5, 4, 2, -1, -2, -4, -5, -5, -6, -7, -5, -6, -7

Offset: 1

Rémy Sigrist, Jun 22 2019

Rémy Sigrist, Table of n, a(n) for n = 1..8191
Rémy Sigrist, Density plot of the first 2^22-1 terms
Rémy Sigrist, PARI program for A326281

See A326280 for the real part of f and additional comment.

Cf. A000120, A023416.

PARI
```
See Links section.
```

A334667 For any number with binary expansion (b_1, ..., b_w), replace the i-th "1" by b_{w+1-i} for i = 1..A000120(n) and the j-th "0" by b_j for j = 1..A023416(n); the resulting binary expansion is that of a(n).

Original entry on oeis.org

0, 1, 1, 3, 2, 6, 3, 7, 4, 12, 6, 14, 3, 11, 7, 15, 8, 24, 10, 26, 9, 25, 14, 30, 6, 22, 13, 29, 7, 23, 15, 31, 16, 48, 18, 50, 17, 49, 22, 54, 18, 50, 25, 57, 21, 53, 30, 62, 12, 44, 28, 60, 14, 46, 29, 61, 7, 39, 23, 55, 15, 47, 31, 63, 32, 96, 34, 98, 33

Offset: 0

Rémy Sigrist, May 08 2020

Fixed points correspond to A000225.

			For n = 41:
- the binary representation of 41 is "101001",
- the 3 1's are replaced by 1, 0, 0, respectively,
- the 3 0's are replaced by 1, 0, 1, respectively,
- hence we obtain "110010",
- and a(41) = 50.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

See A334666 for a similar sequence.

Cf. A000120, A000225, A023416.

a(n) = { my (b=binary(n), t=vector(#b), l=0, r=#b+1); for (k=1, #b, t[k] = if (!b[k], b[l++], b[r--])); fromdigits(t, 2) }

A000120(a(n)) = A000120(n).

A297208 a(0)=0; for n >= 1, a(n) = a(n-1-A023416(n)) + A000120(n).

Original entry on oeis.org

0, 1, 1, 3, 2, 5, 4, 7, 3, 6, 9, 9, 8, 12, 11, 15, 10, 14, 13, 13, 12, 16, 16, 20, 14, 19, 23, 23, 22, 27, 26, 31, 24, 24, 29, 34, 33, 27, 32, 37, 36, 30, 35, 40, 39, 39, 44, 44, 42, 42, 47, 46, 45, 51, 50, 56, 48, 54, 60, 59, 58, 64, 63, 69, 55, 61, 60, 66, 65, 58, 64, 70, 62, 68

Offset: 0

Ctibor O. Zizka, Dec 27 2017

			For n = 7, A023416(7) = 0, A000120(7) = 3 so a(7) = a(6) + 3 , a(6) = a(4) + 2, a(4) = a(1) + 1 , a(1) = a(0) + 1 , a(0) = 0. Thus a(7)= 0 + 1 + 1 + 2 + 3 = 7.

Amiram Eldar, Table of n, a(n) for n = 0..10000
B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), Article 07.7.1.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, J. Integer Sequences, Vol. 9 (2006), Article 06.1.8.

Cf. A023416, A000120.

a[0] = 0; a[n_] := a[n] = a[n - 1 - DigitCount[n, 2, 0]] + DigitCount[n, 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 20 2023 *)

a(n) = if (n==0, 0, a(n-1-#binary(n)+hammingweight(n)) + hammingweight(n)); \\ Michel Marcus, Dec 27 2017

A297212 a(0)=1; a(1)=1; for n >= 2, a(n) = a(A023416(n)) + a(A000120(n)).

Original entry on oeis.org

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

Offset: 0

Ctibor O. Zizka, Dec 27 2017

			n=7, A000120(7)=3, A023416(7)=0. a(7)=a(3)+a(0), a(3)=a(2)+a(0), a(2)=a(1)+a(1). So a(7) = a(1)+a(1)+a(0)+a(0) = 2*a(0) + 2*a(1) = 4.

Michael De Vlieger, Table of n, a(n) for n = 0..10000
B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, J. Integer Sequences, Vol. 9 (2006), #06.1.8.

Cf. A000120, A023416.

a[0] = a[1] = 1; a[n_] := a[n] = a[#1] + a[#2] & @@ DigitCount[n, 2]; Array[a, 90, 0] (* Michael De Vlieger, Mar 16 2022 *)

a(n) = if (n<=1, 1, a(hammingweight(n)) + a(#binary(n)-hammingweight(n)));

More terms from Michel Marcus, Mar 16 2022

A297216 a(0)=1; a(1)=1; for n >= 2, a(n) = a(n-A000120(n)) + a(n-1-A023416(n)).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 8, 12, 16, 20, 28, 36, 48, 64, 84, 120, 156, 184, 240, 312, 396, 480, 624, 792, 1020, 1248, 1584, 2040, 2496, 3288, 4080, 5664, 7248, 8160, 10536, 12912, 16200, 18696, 23448, 29112, 36360, 42144, 52560, 65472, 78504, 94704, 118032, 147264, 183504, 212736

Offset: 0

Ctibor O. Zizka, Dec 27 2017

for n >= 6, a(n) = k(n) * (a(0) + 3*a(1)).

			n=7, A000120(7)=3, A023416(7)=0. a(7) = a(4)+a(6) = a(3)+a(1)+a(4)+a(4) = 3*(a(3)+a(1)) = 3*(a(1)+a(2)+a(1)) = 3*(a(0)+3*a(1)). a(7)=12; k(7)=3.

B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), Article 07.7.1.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, J. Integer Sequences, Vol. 9 (2006), Article 06.1.8.

Cf. A000120, A023416.

A297216 := proc(n)
    option remember ;
    if n <=1 then
        1;
    else
        procname(n-wt(n))+procname(n-1-A023416(n)) ;
    end if;
end proc:
seq(A297216(n),n=0..30) ; # R. J. Mathar, Jun 19 2021

a[0] = a[1] = 1; a[n_] := a[n] = a[n - DigitCount[n, 2, 1]] + a[n - 1 - DigitCount[n, 2, 0]]; Array[a, 50, 0] (* Amiram Eldar, Aug 01 2023 *)

a(n) = if (n<=1, 1, a(n-hammingweight(n)) + a(n-1-(#binary(n)-hammingweight(n)))); \\ Michel Marcus, Dec 27 2017

More terms from Michel Marcus, Dec 27 2017

Offset corrected by R. J. Mathar, Jun 19 2021

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)b(A053645(n)) + [A036987(n) = 0]b(A266341(n)) for n > 0 with b(0) = 1.

Original entry on oeis.org

1, 2, 6, 23, 106, 566, 3415, 22872, 167796, 1334596, 11414192, 104270906, 1011793389, 10379989930, 112134625986, 1271209859403, 15077083642150, 186588381229340, 2403775013224000, 32168379148440968, 446341838086450308, 6410107231501731012, 95136428354649665256

Offset: 0

Mikhail Kurkov, Jun 11 2023 [verification needed]

nonn

Note that [A036987(n) = 0]*b(A266341(n)) is the same as max((1 - T(n, j))*b(A053645(n) + 2^j*(1 - T(n, j))) | 0 <= j <= A000523(n)) where T(n, k) = floor(n/2^k) mod 2.

In fact b(n) is a generalization of A347205 just as A329369 is a generalization of A341392.

Cf. A000523, A023416, A036987, A053645, A266341.

Similar recurrences: A284005, A329369, A341392, A347205.

A063250(n)=my(L=logint(n, 2), A=0); for(i=0, L, my(B=n\2^(L-i)+1); A++; A-=logint(B, 2)==valuation(B, 2)); A
upto(n)=my(v, v1); v=vector(2^n, i, 0); v[1]=1; v1=vector(n+1, i, 0); v1[1]=1; for(i=1, #v-1, my(L=logint(i, 2), A=i - 2^L, B=A063250(i)); v[i+1]=(L - hammingweight(i) + 2)*v[A+1] + if(B>0, v[A + 2^(B-1) + 1])); for(i=1, n, v1[i+1]=v1[i] + sum(j=2^(i-1)+1, 2^i, v[j])); v1

cp's OEIS Frontend

A216431 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A023416.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

Extensions

A334666 For any number with binary expansion (b_1, ..., b_w), replace the i-th "1" by b_i for i = 1..A000120(n) and the j-th "0" by b_{w+1-j} for j = 1..A023416(n); the resulting binary expansion is that of a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A100921 n appears A023416(n) times (appearances equal number of 0-bits).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A326280 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)*g((1+i)^(A000120(n)-1) * (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the real part of f(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A326281 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)*g((1+i)^(A000120(n)-1) * (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the imaginary part of f(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A334667 For any number with binary expansion (b_1, ..., b_w), replace the i-th "1" by b_{w+1-i} for i = 1..A000120(n) and the j-th "0" by b_j for j = 1..A023416(n); the resulting binary expansion is that of a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A297208 a(0)=0; for n >= 1, a(n) = a(n-1-A023416(n)) + A000120(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A297212 a(0)=1; a(1)=1; for n >= 2, a(n) = a(A023416(n)) + a(A000120(n)).

Views

Author

Keywords

Examples

Links

A326280 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)g((1+i)^(A000120(n)-1) (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the real part of f(n).

A326281 Let f(n) be a sequence of distinct Gaussian integers such that f(1) = 0 and for any n > 1, f(n) = f(floor(n/2)) + k(n)g((1+i)^(A000120(n)-1) (1-i)^A023416(n)) where k(n) > 0 is as small as possible and g(z) = z/gcd(Re(z), Im(z)); a(n) is the imaginary part of f(n).

A363417 a(n) = Sum_{j=0..2^n - 1} b(j) for n >= 0 where b(n) = (A023416(n) + 1)b(A053645(n)) + [A036987(n) = 0]b(A266341(n)) for n > 0 with b(0) = 1.