A057168 -id:A057168 - cp's OEIS frontend

A381405 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) AND a(n-1) = 0, where AND is the binary AND operation, while the binary weight of a(n) does not equal that of a(n-1).

0, 1, 6, 8, 3, 4, 9, 2, 5, 16, 7, 24, 32, 10, 21, 34, 13, 18, 37, 64, 11, 20, 35, 12, 19, 36, 25, 66, 28, 33, 14, 17, 38, 65, 22, 40, 23, 72, 39, 80, 15, 48, 67, 60, 128, 26, 68, 27, 96, 29, 98, 129, 30, 97, 130, 41, 86, 136, 49, 78, 144, 42, 85, 138, 53, 74, 132, 43, 84, 139, 52, 75, 148, 99, 140, 51, 76, 147, 44, 83, 160, 31, 192, 45, 82, 141, 50, 77, 146, 101

Offset: 0

Scott R. Shannon, Feb 22 2025

In the first 100000 terms the fixed points are 0, 1, 28, 76, 543, 1580, although more likely exist.

			a(3) = 8 = 1000_2 as 8 is unused and a(2) = 6 = 110_2, and 1000_2 AND 110_2 = 0 while the binary weights of 8 and 6 are 1 and 2 respectively.

Scott R. Shannon, Table of n, a(n) for n = 0..10000

Cf. A000120, A129760, A061712, A057168, A381406.

A381406 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) OR a(n-1) = 2^k - 1, where OR is the binary OR operation and k>=1, while the binary weight of a(n) does not equal that of a(n-1).

Original entry on oeis.org

0, 1, 3, 2, 5, 7, 4, 11, 6, 13, 10, 15, 8, 23, 9, 14, 17, 30, 19, 12, 27, 20, 31, 16, 47, 18, 29, 22, 43, 21, 46, 25, 39, 24, 55, 26, 45, 50, 61, 34, 63, 28, 51, 44, 59, 36, 91, 37, 58, 69, 62, 33, 94, 35, 60, 67, 124, 71, 56, 79, 48, 95, 32, 127, 38, 57, 70, 121, 54, 41, 86, 107, 52, 75, 117, 42, 53, 74, 119, 40, 87, 104, 151, 105, 118, 73, 126, 49, 78, 115

Offset: 0

Scott R. Shannon, Feb 22 2025

The fixed points begin 0, 1, 10, 315, 413, 415, 1551, 1559, 1797; there are likely infinitely more.

			a(4) = 5 = 101_2 as 5 is unused and a(3) = 2 = 10_2, and 101_2 OR 10_2 = 111_2 = 2^3 - 1, while the binary weights of 5 and 2 are 2 and 1 respectively.

Scott R. Shannon, Table of n, a(n) for n = 0..10000

Cf. A000120, A086799, A061712, A057168, A381405.

A287076 a(n) = least k > n with the same sum of digits as n in some base b > 1.

Original entry on oeis.org

2, 4, 5, 6, 6, 9, 10, 12, 10, 12, 13, 16, 14, 16, 19, 20, 18, 20, 21, 22, 22, 24, 25, 30, 26, 28, 29, 30, 30, 36, 33, 34, 34, 36, 37, 40, 38, 40, 42, 42, 42, 44, 45, 48, 46, 48, 49, 56, 50, 52, 53, 56, 54, 57, 57, 58, 58, 60, 61, 64, 62, 66, 67, 66, 66, 68, 69

Offset: 1

Rémy Sigrist, May 19 2017

More formally: a(n) = Min_{b>1} f_b(n), where f_b(n) = least k > n with the same sum of digits as n in base b.
We have the following properties:
- f_b(b) = b^2 for any b > 1,
- f_b(b^k) = b^(k+1) for any b > 1 and k >= 0,
- f_b(n) = b + n - 1 for any b > 1 and n < b,
- f_b(n) - n >= b - 1 for any b > 1 and n > 0.
Also, f_2 = A057168 and f_10 = A228915.
For any n > 0, n < a(n) <= 2*n.
Conjecturally, a(n) ~ n.
The derived sequence e(n) = a(n) - n is unbounded: for any n > 0:
- for any b such that 1 < b <= n, let x_b = the least power of b such that f_b(i*x_b) - i*x_b >= n for any i > 0,
- let X = Lcm_{b=2..n} x_b,
- then f_b(X) - X >= n for any b such that 1 < b <= n,
- also, f_b(X) - X >= b - 1 >= n for any b > n,
- hence a(X) - X = e(X) >= n, QED.

			The following table shows f_b(8) for all bases b > 1:
b    f_b(8)   8 in base b   f_b(8) in base b
--   ------   -----------   ----------------
2        16        "1000"            "10000"
3        14          "22"              "112"
4        17          "20"              "101"
5        12          "13"               "22"
6        13          "12"               "21"
7        14          "11"               "20"
8        64          "10"              "100"
b>8     b+7           "8"               "17"
Hence, a(8) = f_5(8) = 12.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A287076

Cf. A057168, A228915.

A306441 Next larger integer with same number of runs of 1's in its binary representation as n.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Feb 15 2019

Number of runs of 1's in binary representation is given by A069010.

Each nonnegative number either appears in this sequence or in A002450.

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   1     2       1         10
   2     3      10         11
   3     4      11        100
   4     6     100        110
   5     9     101       1001
   6     7     110        111
   7     8     111       1000
   8    12    1000       1100
   9    10    1001       1010
  10    11    1010       1011
  11    13    1011       1101
  12    14    1100       1110
  13    17    1101      10001
  14    15    1110       1111
  15    16    1111      10000
  16    24   10000      11000

Cf. A002450, A023758, A043682, A043683, A043684, A043685, A043686, A057168, A069010.

r1(n) = my (c=0); while (n, my (v=valuation(n+(n%2),2)); if (n%2, c++); n\=2^v); c
a(n) = my (r=r1(n)); for (k=n+1, oo, if (r==r1(k), return (k)))

a(A023758(n)) = A023758(n+1) for any n > 1.
a(A043682(n)) = A043682(n+1) for any n > 0.
a(A043683(n)) = A043683(n+1) for any n > 0.
a(A043684(n)) = A043684(n+1) for any n > 0.
a(A043685(n)) = A043685(n+1) for any n > 0.
a(A043686(n)) = A043686(n+1) for any n > 0.

A340162 a(1) = 7; thereafter a(n) is the smallest number k with exactly three 1-bits, not already in the sequence, for which k*a(n - 1) has exactly three 1-bits (A014311).

Original entry on oeis.org

7, 14, 19, 28, 37, 56, 38, 112, 74, 224, 76, 448, 148, 896, 152, 1792, 296, 3584, 304, 7168, 592, 14336, 608, 28672, 1184, 57344, 1216, 114688, 2368, 229376, 2432, 458752, 4736, 917504, 4864, 1835008, 9472, 3670016, 9728, 7340032, 18944, 14680064, 19456, 29360128

Offset: 1

Marius A. Burtea, Dec 30 2020

It seems that a(2*k) = 2^k*7, a(4*k - 1) = 2^(k - 1)*19, a(4*k + 1) = 2^(k - 1)*37, k >= 1.

			a(1) * a(2) = 7 * 14 = A014311(1) * A014311(4) = A014311(32).
a(2) * a(3) = 14 * 19 = A014311(4) * A014311(5) = A014311(61).
a(3) * a(4) = 19 * 28 = A014311(5) * A014311(10) = A014311(93).

Chai Wah Wu, Table of n, a(n) for n = 1..1000

Cf. A014311, A057168.

fb:=func; a:=[7]; for n in [2..44] do k:=7; while k in a or (not fb(k) or not fb(a[n-1]*k)) do k:=k+1; end while; Append(~a,k); end for; a;

isokd(n) = hammingweight(n) == 3; \\ A014311
nexth(n) = my(u=bitand(n, -n), v=u+n); (bitxor(v, n)/u)>>2+v; \\ A057168
nextk(va, n) = {my(ok = 0, k = 7); while (! (isokd(k*va[n-1]) && !#select(x->(x==k), va)), k = nexth(k)); k;}
lista(nn) = {my(va = vector(nn)); va[1] = 7; for (n=2, nn, my(k = nextk(va, n)); va[n] = k;); va; } \\ Michel Marcus, Jan 14 2021

Conjectures from Chai Wah Wu, Jan 27 2021: (Start)
a(n) = 2*a(n-2) + 2*a(n-4) - 4*a(n-6) for n > 7.
G.f.: x*(-46*x^6 - 28*x^5 - 15*x^4 + 5*x^2 + 14*x + 7)/((2*x^2 - 1)*(2*x^4 - 1)). (End)

A341944 Next larger integer with same number of runs in binary expansion as n.

Original entry on oeis.org

3, 4, 7, 6, 9, 8, 15, 12, 11, 18, 13, 14, 17, 16, 31, 24, 19, 20, 23, 22, 37, 26, 25, 28, 27, 34, 29, 30, 33, 32, 63, 48, 35, 36, 39, 38, 41, 40, 47, 44, 43, 74, 45, 46, 53, 50, 49, 56, 51, 52, 55, 54, 69, 58, 57, 60, 59, 66, 61, 62, 65, 64, 127, 96, 67, 68

Offset: 1

Rémy Sigrist, Feb 24 2021

Number of runs in binary expansion is given by A005811.

This is a permutation of A107907.

			The first terms in decimal and in binary, alongside A005811(n), are:
  n   a(n)  bin(n)  bin(a(n))  A005811(n)
  --  ----  ------  ---------  ----------
   1     3       1         11           1
   2     4      10        100           2
   3     7      11        111           1
   4     6     100        110           2
   5     9     101       1001           3
   6     8     110       1000           2
   7    15     111       1111           1
   8    12    1000       1100           2
   9    11    1001       1011           3
  10    18    1010      10010           4
  11    13    1011       1101           3
  12    14    1100       1110           2

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

Cf. A000975, A005811, A057168, A107907.

a(n) = my (r=hammingweight(bitxor(n, n>>1))); for (k=n+1, oo, if (r==hammingweight(bitxor(k, k>>1)), return (k)))

def runs(n): return bin(n^(n>>1)).count('1')
def a(n):
  nruns, m = runs(n), n + 1
  while runs(m) != nruns: m += 1
  return m
print([a(n) for n in range(1, 67)]) # Michael S. Branicky, Feb 24 2021

A005811(a(n)) = A005811(n).

a(2^k-1) = 2^(k+1)-1 for any k > 0.

A360443 Smallest integer m > n such that the multiset of nonzero decimal digits of m is exactly the same as the multiset of nonzero decimal digits of n.

Original entry on oeis.org

10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 101, 21, 31, 41, 51, 61, 71, 81, 91, 200, 102, 202, 32, 42, 52, 62, 72, 82, 92, 300, 103, 203, 303, 43, 53, 63, 73, 83, 93, 400, 104, 204, 304, 404, 54, 64, 74, 84, 94, 500, 105, 205, 305, 405, 505, 65, 75, 85, 95, 600

Offset: 1

Marc LeBrun and M. F. Hasler, Feb 22 2023

Equivalently: a(n) is the number whose decimal digits are the next larger permutation of those of n, allowing any number of leading zeros.

M. F. Hasler, Table of n, a(n) for n = 1..1000
Wikipedia, Permutation: Generation in lexicographic order, as of Feb. 2023.

Cf. A057168 (analog for base 2), A354049 (digits of a(n) contain those of n as sub-multiset).

Cf. A009994 (numbers with digits in nondecreasing order: don't appear in this sequence).

A360443(n)={forperm(concat(0,digits(n)),p,n||return(fromdigits(Vec(p))); n=0)} \\ M. F. Hasler, Feb 23 2023; similar idea also suggested by Ruud H.G. van Tol.

# From Arthur O'Dwyer, edited by M. F. Hasler, Feb 22 2023
def A360443(n):
    s = '0' + str(n)
    i = next(i for i in range(len(s) - 1, 0, -1) if s[i-1] < s[i])
    tail = s[i-1:]
    j = min((ch, j) for j, ch in enumerate(tail) if s[i-1] < ch)[1]
    s = s[:i-1] + tail[j] + ''.join(sorted(tail[:j] + tail[j+1:]))
    return int(s)
for n in range(1, 100): print(n, A360443(n))

A361079 Number of integers in [n .. 2n-1] having the same binary weight as n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 3, 3, 1, 4, 4, 5, 4, 6, 6, 4, 1, 5, 5, 8, 5, 9, 9, 7, 5, 10, 10, 9, 10, 10, 10, 5, 1, 6, 6, 12, 6, 13, 13, 13, 6, 14, 14, 15, 14, 16, 16, 9, 6, 15, 15, 18, 15, 19, 19, 12, 15, 20, 20, 14, 20, 15, 15, 6, 1, 7, 7, 17, 7, 18, 18, 23, 7, 19, 19

Offset: 0

Alois P. Heinz, Mar 01 2023

Or number of steps it takes to double n, where each step goes to the next larger integer with the same binary weight.

			a(9) = 4: 9 -> 10 -> 12 -> 17 -> 18 or in binary: 1001_2 -> 1010_2 -> 1100_2 -> 10001_2 -> 10010_2.

Alois P. Heinz, Table of n, a(n) for n = 0..20000

Cf. A000079, A000120, A057168, A068076, A263017.

b:= proc(n) option remember; uses Bits; local c, l, k;
      c, l:= 0, [Split(n)[], 0];
      for k while l[k]<>1 or l[k+1]<>0 do c:=c+l[k] od;
      Join([1$c, 0$k-c, 1, l[k+2..-1][]])
    end:
a:= proc(n) option remember; local i, m, t; m, t:=n, 2*n;
      for i from 0 while m<>t do m:= b(m) od; i
    end:
seq(a(n), n=0..100);

f[n_] := f[n] = DigitCount[n, 2, 1]; a[n_] := Count[ Array[f, n, n], f[n]]; Array[a, 75, 0] (* Robert G. Wilson v, Mar 15 2023 *)

a(n) = my(w=hammingweight(n)); sum(k=n, 2*n-1, hammingweight(k) == w); \\ Michel Marcus, Mar 16 2023

from math import comb
def A361079(n):
    c, k = 0, 1
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            c += comb(i+1,k)-comb(i,k)
            k += 1
    return c # Chai Wah Wu, Mar 01 2023

a(n) = |{ k in [n, 2n-1] : A000120(k) = A000120(n) }|.
((x-> A057168(x))^a(n))(n) = 2*n.
a(n) = A068076(2n) - A068076(n) = A263017(2n) - A263017(n).
a(n) = 1 <=> n in { A000079 }.

A377738 a(n) is the least m > n such that the Zeckendorf representations of m and n have the same number of terms.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Nov 05 2024

A permutation of the numbers missing from A027941.
To compute a(n):
- in the Zeckendorf representation of n,
- locate the rightmost term A000045(k) such that A000045(k+2) is not a term,
- replace A000045(k) by A000045(k+1),
- replace the c terms < A000045(k) by A027941(c).

			The first terms, alongside their Zeckendorf representations, are:
  n   a(n)  A014417(n)  A014417(a(n))
  --  ----  ----------  -------------
   1     2           1             10
   2     3          10            100
   3     5         100           1000
   4     6         101           1001
   5     8        1000          10000
   6     7        1001           1010
   7     9        1010          10001
   8    13       10000         100000
   9    10       10001          10010
  10    11       10010          10100
  11    14       10100         100001
  12    17       10101         100101
  13    21      100000        1000000
  14    15      100001         100010

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences related to Zeckendorf expansion of n

Cf. A000045, A003714, A007895, A014417, A027941, A057168, A228915.

PARI
```
\\ See Links section.
```

a(A000045(k)) = A000045(k+1) for any k >= 2.

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

Original entry on oeis.org

2, 1, 5, 2, 6, 5, 11, 4, 10, 9, 13, 10, 14, 13, 23, 8, 18, 17, 21, 18, 22, 21, 27, 20, 26, 25, 29, 26, 30, 29, 47, 16, 34, 33, 37, 34, 38, 37, 43, 36, 42, 41, 45, 42, 46, 45, 55, 40, 50, 49, 53, 50, 54, 53, 59, 52, 58, 57, 61, 58, 62, 61, 95, 32, 66, 65, 69, 66

Offset: 1

Chai Wah Wu, Mar 06 2025

nonn

a(n) = integer m nearest to n such that m <> n and A000120(n) = A000120(m).
Theorem: a tie does not occur for n>0, i.e. A057168(n)-n <> n-A243109(n).
Proof: If n is of the form 2^k-1, then there are no smaller numbers with the same Hamming weight as n and a(n) = A057168(n) = (3n+1)/2.
If n is of the form (2^k-1)*2^m for some k,m>0, then n in binary is of the form 11..1100..00 and A057168(n) = 2^(k+m)+2^(k-1)-1, i.e. 100..0011..11 in binary. On the other hand, A243109(n) = (2^(k-1)-1)*2^(m+1)+2^(m-1), i.e. 11..110100..00 in binary. Thus A057168(n)-n = 2^(k-1)-1+2^m >= 2^m and n-A243109(n) = 2^(m-1) < 2^m. There is no tie and a(n) = A243109(n).
If n is not of the form (2^k-1)*2^m, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2^r-1, then A243109(n) must flip one of the '1' bit in xxx...xxx whereas A057168(n) leaves xxx...xxx unchanged. Thus n-A243109(n) > A057168(n)-n. Otherwise A057168(n) and A243109(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.
The above also gives a procedure to determine when a(n) = A057168(n) and when a(n) = A243109(n) or more succinctly a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.

			For n = 2, A057168(2) = 4 and A243109(2) = 1 and 1 is closer to 2 than 4, thus a(2) = 1.

Robert Israel, Table of n, a(n) for n = 1..10000
Marc B. Reynolds, Popcount walks: next, previous, toward and nearest (2023).

Cf. A000120, A055010, A057168, A243109.

f:= proc(n) local t,k,d;
  if n::even then d:=-1 else d:= 1 fi;
  t:= convert(convert(n,base,2),`+`);
  for k from n+d by d do
    if convert(convert(k,base,2),`+`) = t then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Jun 20 2025

def A381764(n): return n^((a:=-n&n+1)|(a>>1))

a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.
a(2^k-1) = A055010(k).
For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3).

cp's OEIS Frontend

A381405 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) AND a(n-1) = 0, where AND is the binary AND operation, while the binary weight of a(n) does not equal that of a(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A381406 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) OR a(n-1) = 2^k - 1, where OR is the binary OR operation and k>=1, while the binary weight of a(n) does not equal that of a(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A287076 a(n) = least k > n with the same sum of digits as n in some base b > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A306441 Next larger integer with same number of runs of 1's in its binary representation as n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A340162 a(1) = 7; thereafter a(n) is the smallest number k with exactly three 1-bits, not already in the sequence, for which k*a(n - 1) has exactly three 1-bits (A014311).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

PARI

Formula

A341944 Next larger integer with same number of runs in binary expansion as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A360443 Smallest integer m > n such that the multiset of nonzero decimal digits of m is exactly the same as the multiset of nonzero decimal digits of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A361079 Number of integers in [n .. 2n-1] having the same binary weight as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica