A004754 -id:A004754 - cp's OEIS frontend

A218615 a(n) = binary code (shown here in decimal) of the position of natural number n in the beanstalk-tree A218776.

1, 3, 2, 6, 4, 14, 10, 26, 18, 58, 42, 122, 90, 106, 74, 202, 138, 458, 330, 970, 714, 842, 586, 1866, 1354, 1610, 1098, 3402, 2378, 3658, 2634, 6730, 4682, 14922, 10826, 31306, 23114, 27210, 19018, 59978, 43594, 51786, 35402, 109130, 76362, 117322, 84554, 248394

Offset: 1

Antti Karttunen, Nov 16 2012

The binary code is the same as used by function general-car-cdr of MIT/GNU Scheme: a zero bit represents a cdr operation (taking the right hand side branch in the binary tree), and a one bit represents a car (taking the left hand side branch in the binary tree). The bits are interpreted from LSB to MSB, and the most significant one bit, rather than being interpreted as an operation, signals the end of the binary code.

			As we can traverse to 4 in A218776-tree (see the example there) by taking first the right branch (cdr) from the root, resulting bit 0 as the least significant bit of the code, then by taking the left branch (car) from 3 to get to 4, resulting bit 1 as the second rightmost bit of the code, which when capped with an extra termination-one, results binary code 110, 6 in decimal, thus a(4)=6.

A. Karttunen, Table of n, a(n) for n = 1..1024
MIT/GNU Scheme 9.1. documentation, Function general-car-cdr

a(n) = A054429(A218614(n)). Superset of A218791. Used to construct A218776, A218777. Cf. also A179016, A218787, A218788

a(1)=1, for odd n, a(n) = A004754(a(A011371(n))), for even n, a(n) = A004755(a(A011371(n))).

A218790 a(n) = binary code (shown here in decimal) of the position of the predecessor of the natural number pair (2n,2n+1) in the compact beanstalk-tree A218782.

Original entry on oeis.org

1, 3, 5, 13, 21, 37, 53, 117, 181, 309, 437, 693, 949, 1717, 1461, 3509, 5557, 9653, 13749, 21941, 30133, 54709, 46517, 79285, 112053, 210357, 177589, 472501, 308661, 734645, 996789, 2045365, 3093941, 5191093, 7288245, 11482549, 15676853, 28259765, 24065461

Offset: 1

Antti Karttunen, Nov 16 2012

Antti Karttunen, Table of n, a(n) for n = 1..1024

Subset of A218614, i.e. a(n) = A218614(A005187(n)).

Also, a(n) = A054429(A218791(n)). Used to construct A218782, A218783. Cf. also A218787, A218788

a(n) = A218614(A005187(n)).

A218791 a(n) = binary code (shown here in decimal) of the position of the predecessor of the natural number pair (2n,2n+1) in the compact beanstalk-tree A218780.

Original entry on oeis.org

1, 2, 6, 10, 26, 58, 42, 74, 202, 458, 330, 842, 586, 1354, 1610, 2634, 6730, 14922, 10826, 27210, 19018, 43594, 51786, 117322, 84554, 182858, 215626, 313930, 477770, 838218, 576074, 1100362, 3197514, 7391818, 5294666, 13683274, 9488970, 22071882, 26266186

Offset: 1

Antti Karttunen, Nov 16 2012

A. Karttunen, Table of n, a(n) for n = 1..1024

Subset of A218615, i.e., a(n) = A218615(A005187(n)).
Also, a(n) = A054429(A218790(n)). (Note also how the first five or so terms are twice the terms in the beginning of A218790, shifted by one term.)
Used to construct A218780, A218781. Cf. also A218787, A218788.

a(n) = A218615(A005187(n)).

A123001 Binary numbers that start 10...

Original entry on oeis.org

10, 100, 101, 1000, 1001, 1010, 1011, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 101111

Offset: 1

N. J. A. Sloane, Oct 11 2010

T. D. Noe, Table of n, a(n) for n=1..1023

See A004754 for their decimal equivalents.

A255069 First differences of A255071.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 24, 44, 81, 150, 280, 526, 992, 1875, 3551, 6740, 12823, 24450, 46709, 89383, 171325, 328962, 632849, 1219909, 2356217, 4559224, 8835610, 17144046, 33295497, 64705083, 125802338, 244673791, 476011284, 926373373, 1803512210, 3512774806

Offset: 1

Antti Karttunen, Feb 21 2015

nonn

Also, a(n) = the number of times a number whose binary expansion begins with 10... (cf. A004754) is encountered when iterating from 2^(n+2)-2 to (2^(n+1))-2 with the map x -> x - (number of runs in binary representation of x), i.e., with m(n) = A236840(n). For example, when starting from the initial value (2^(4+2))-2 = 62, we get m(62) = 60, m(60) = 58, m(58) = 54, m(54) = 50, m(50) = 46, m(46) = 42, m(42) = 36 and finally m(36) = 32, which is (2^(4+1)). Of the nine numbers encountered, only 46, 42, 36 and 32 (in binary: 101110, 101010, 100100 and 100000) are in A004754, thus a(4) = 5.

First differences of A255071.
Cf. A004754, A005811, A236840, A255061, A255062, A255056, A255066.
Cf. also A255063, A255064, A255125, A255126.
Analogous sequence: A226060.

(define (A255069 n) (- (A255071 (+ n 1)) (A255071 n)))
(define (A255069shifted n) (add (lambda (n) (- 1 (A079944off2 (A255066 n)))) (A255062 n) (A255061 (+ 1 n)))) ;; Cf. A079444.

a(n) = A255071(n+1) - A255071(n).
For n > 1, a(n-1) = Sum_{k = A255062(n) .. A255061(n+1)}(1-secondmsb(A255056(k))).
Here secondmsb is implemented by the starting offset 2 version of A079944, and effectively gives the second most significant bit in the binary expansion of n. The formula follows from the semi-regular nature of number-of-runs beanstalk, see comments above and at A255071.

A122872 Table by antidiagonals, T(n,k) is k-th number that starts with n in binary representation.

Original entry on oeis.org

1, 2, 2, 3, 4, 3, 4, 5, 6, 4, 5, 8, 7, 8, 5, 6, 9, 12, 9, 10, 6, 7, 10, 13, 16, 11, 12, 7, 8, 11, 14, 17, 20, 13, 14, 8, 9, 16, 15, 18, 21, 24, 15, 16, 9, 10, 17, 24, 19, 22, 25, 28, 17, 18, 10, 11, 18, 25, 32, 23, 26, 29, 32, 19, 20, 11, 12, 19, 26, 33, 40, 27, 30, 33, 36, 21, 22, 12

Offset: 1

Franklin T. Adams-Watters, Oct 23 2006

In rows n through 2n-1, every integer >= n occurs exactly once.

			Top left corner is:
1 2 3 4 5
2 4 5 8 9
3 6 7 12 13
4 8 9 16 17
5 10 11 20 21

Rows: A000027, A004754, A004755, A004756, A004757, A004758, A004759. Algebraically, A053645 would be row zero, minus A080079 would be row minus one. See also A053644.

T(n,1) = n; T(n,2k) = 2T(n,k); T(n,2k+1) = 2T(n,k) + 1. T(n,k) = k + (n-1) * 2^floor(log_2(k)) = k + (n-1)*A053644(k).

A294523 Lexicographically earliest sequence of positive terms, such that, for any n > 0, the binary expansion of n, say of size k+1, is (1, a(n) mod 2, a^2(n) mod 2, ..., a^k(n) mod 2) (where a^i denotes the i-th iterate of the sequence).

Original entry on oeis.org

1, 2, 1, 2, 6, 5, 1, 2, 10, 6, 14, 9, 5, 13, 1, 2, 18, 10, 22, 12, 6, 14, 30, 17, 9, 5, 11, 25, 13, 29, 1, 2, 34, 18, 38, 20, 10, 22, 46, 24, 12, 6, 54, 28, 14, 30, 62, 33, 17, 9, 19, 41, 5, 11, 23, 49, 25, 13, 27, 57, 29, 61, 1, 2, 66, 34, 70, 36, 18, 38, 78

Offset: 1

Rémy Sigrist, Nov 01 2017

More informally, the parity of the iterate of the sequence at n gives the binary expansion of n (beyond the leading 1).
Apparently, iterating the sequence always leads to one of these three loops:
- the fixed point (1) iff we start from 2^k-1 for some k > 0,
- the fixed point (2) iff we start from 2^k for some k > 0,
- or (5, 6) for any other starting value.
a(n) is even iff n belongs to A004754.
a(n) is odd iff n belongs to A004760.
If a(n) > n then a(n) = A080541(n).
If n < 2^k then a(n) < 2^k.
Apparently, if a(n) > 2, then A054429(a(n)) = a(A054429(n)); this accounts for the symmetry of the part connected to the loop (5,6) in the oriented graph of this sequence.

			For n=11:
- the binary representation of 11 is (1,0,1,1),
- a(11) = 14 has parity 0,
- a(14) = 13 has parity 1,
- a(13) = 5 has parity 1,
- we find the binary digits of 11 beyond the initial 1, in order: 0, 1, 1.
See also representations of first terms in Links section.

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, Representation of the first 32 terms as an oriented graph (n -> a(n))
Rémy Sigrist, Representation of the first 64 terms as an oriented graph (n -> a(n))
Rémy Sigrist, PARI program for A294523

Cf. A000079, A000225, A000975, A004754, A004760, A052997, A054429, A080541, A081253, A081254, A266248, A266613, A266721, A267045.

PARI
```
See Links section.
```

a(n) = 1 iff n = A000225(k) for some k > 0.
a(n) = 2 iff n = A000079(k) for some k > 0.
a(n) = 5 iff n = A081254(k) for some k > 2.
a(n) = 6 iff n = A000975(k) for some k > 2.
a(n) = 10 iff n = A081253(k) for some k > 2.
a(n) = 12 iff n = A266613(k) for some k > 3.
a(n) = 13 iff n = A052997(k) for some k > 2.
a(n) = 14 iff n = A266721(k) for some k > 2.
a(n) = 18 iff n = A267045(k) for some k > 3.
a(n) = 54 iff n = A266248(k) for some k > 4.
These formulas come from the fact that each sequence on the right side, say f, eventually satisfies: f(n) = floor(f(n+1)/2), and f(n) and f(n+2) have the same parity.

A309736 a(1) = 1, and for any n > 1, a(n) is the least k > 0 such that the binary representation of n^k starts with "10".

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 2, 2, 3, 5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 5, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 5, 6, 10, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Rémy Sigrist, Aug 14 2019

The sequence is well defined; for any n > 0:
- if n is a power of 2, then a(n) = 1,
- if n is not a power of 2, then log_2(n) is irrational,
  hence the function k -> frac(k * log_2(n)) is dense in the interval [0, 1]
  according to Weyl's criterion,
  so for some k > 0, k*log_2(n) = m + 1 + e where m is a positive integer
                                              and 0 <= e < log_2(3) - 1 < 1,
- hence 2 * 2^m <= n^k < 3 * 2^m and a(n) <= k, QED.

			For n = 7:
- the first powers of 7, in decimal as well as in binary, are:
    k  7^k  bin(7^k)
    -  ---  ---------
    1    7        111
    2   49     110001
    3  343  101010111
- hence a(7) = 3.

Rémy Sigrist, Scatterplot of (x, y) such that the binary representation of x^y starts with "10" and x = 2..1024 and y = 1..1024
Eric Weisstein's World of Mathematics, Weyl's Criterion

Cf. A004754, A090996, A098174.

a(n) = { my (nk=n); for (k=1, oo, if (binary(2*nk)[2]==0, return (k), nk *= n)) }

a(n) = 1 iff n belongs to A004754.
a(2*n) = a(n).
A090996(n^a(n)) = 1.

A354901 a(n) = (b(2n) - 1)/2 - n for n > 0. To get b(n) start with A = n and then for i = 0..f(n) apply A := A + 2^i*T(A, f(n) - i) where T(n, k) = floor(n/2^k) mod 2 and f(n) = A000523(n).

Original entry on oeis.org

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

Offset: 1

Mikhail Kurkov, Jun 11 2022

nonn

Subsequences from a(2^m) to a(2^(m+1) - 1) for m >= 0 contain all numbers k such that 2^m <= k < 2^(m+1). This fact was proved (see Peter J. Taylor link).

Peter J. Taylor, Permutation of the natural numbers from operation related to binary expansion of n, answer to question on MathOverflow (2023).
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences related to binary expansion of n

Cf. A000523, A004754, A059893.

b(n)=my(L=logint(n,2),A=n); for(i=0,L, A+=2^i*bittest(A,L-i)); A;
a(n)=(b(2*n) - 1)/2 - n

cp's OEIS Frontend

A218615 a(n) = binary code (shown here in decimal) of the position of natural number n in the beanstalk-tree A218776.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A218790 a(n) = binary code (shown here in decimal) of the position of the predecessor of the natural number pair (2n,2n+1) in the compact beanstalk-tree A218782.

Views

Author

Keywords

Links

Crossrefs

Formula

A218791 a(n) = binary code (shown here in decimal) of the position of the predecessor of the natural number pair (2n,2n+1) in the compact beanstalk-tree A218780.

Views

Author

Keywords

Links

Crossrefs

Formula

A123001 Binary numbers that start 10...

Views

Author

Keywords

Links

Crossrefs

A255069 First differences of A255071.

Views

Author

Keywords

Comments

Crossrefs

Programs

Scheme

Formula

A122872 Table by antidiagonals, T(n,k) is k-th number that starts with n in binary representation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A294523 Lexicographically earliest sequence of positive terms, such that, for any n > 0, the binary expansion of n, say of size k+1, is (1, a(n) mod 2, a^2(n) mod 2, ..., a^k(n) mod 2) (where a^i denotes the i-th iterate of the sequence).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A309736 a(1) = 1, and for any n > 1, a(n) is the least k > 0 such that the binary representation of n^k starts with "10".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354901 a(n) = (b(2n) - 1)/2 - n for n > 0. To get b(n) start with A = n and then for i = 0..f(n) apply A := A + 2^i*T(A, f(n) - i) where T(n, k) = floor(n/2^k) mod 2 and f(n) = A000523(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI