A213709 -id:A213709 - cp's OEIS frontend

A218600 Partial sums of A213709.

0, 1, 2, 4, 7, 12, 21, 38, 68, 122, 220, 399, 729, 1343, 2493, 4655, 8727, 16405, 30901, 58319, 110298, 209098, 397407, 757296, 1446945, 2771951, 5323982, 10250571, 19780122, 38243220, 74058513, 143592684, 278661808, 541110611, 1051158027, 2042539460, 3969857205

Offset: 0

Antti Karttunen, Nov 05 2012

nonn

a(n) tells the position of (2^n)-1 in A179016.

a(n) = A213710(n)-1. A179016(a(n))=(2^n)-1. Cf. A213711.

a(29)-a(36) from Alois P. Heinz, Jul 03 2022

A218602 Simple self-inverse permutation of natural numbers: after zero, list each block of A213709(n) numbers in reverse order, from A218600(n) to A213710(n-1).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 10 2012

nonn

This permutation can be used to map between the sequences A179016 and A218616. E.g. A179016(n) = A218616(a(n)) and vice versa: A218616(n) = A179016(a(n)).

Antti Karttunen, Table of n, a(n) for n = 0..8727
Index entries for sequences that are permutations of the natural numbers

Cf. A179016, A218616, A054429, A130918, A054430.

(define (A218602 n) (- (A218600 (A213711 n)) (A218601 n)))

a(n) = A218600(A213711(n))-A218601(n).

A218601 After the first zero, integers from 0 to A213709(n)-1 followed by integers from 0 to A213709(n+1)-1, etc.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 10 2012

nonn

Antti Karttunen, Table of n, a(n) for n = 0..8727

Needed for A218602. Cf. also A218599, A053645, A082853, A002262.

(define (A218601 n) (if (zero? n) n (-1+ (- n (A218600 (-1+ (A213711 n)))))))

a(0)=0, and for n>0, a(n) = (n-A218600(A213711(n)-1))-1.

A226060 First differences of A213709.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 13, 24, 44, 81, 151, 284, 536, 1012, 1910, 3606, 6818, 12922, 24561, 46821, 89509, 171580, 329760, 635357, 1227025, 2374558, 4602962, 8933547, 17352195, 33718878, 65534953, 127379679, 247598613, 481334017, 935936312, 1820567772, 3543113588

Offset: 0

Antti Karttunen, Jun 12 2013

nonn

Also, apart from the first term a(0)=0, the number of terms in A179016 whose binary width is n+2 bits and whose two most significant bits are both ones. For example, there is one term 7 (111) in three-bit range; one term 15 (1111) in four bit range; two such terms, 26 (11010) and 31 (11111) in five-bit range; four terms: 49, 53, 57, 63 in six-bit range and eight terms: 97, 101, 104, 109, 112, 116, 120, 127 in seven-bit range.
For n >= 4, a(n) = number of steps to go from 2^(n+2) to (2^(n+1) + 2^n + 1) using the iterative process described in A071542.
Ratio a(n)/A213709(n) develops as: 0, 1, 0.5, 0.667..., 0.8, 0.889..., 0.765..., 0.8, 0.815..., 0.827..., 0.844..., 0.861..., 0.873..., 0.88..., 0.883..., 0.886..., 0.888..., 0.891..., 0.896..., 0.901..., 0.906..., 0.911..., 0.916..., 0.921..., 0.926..., 0.93..., 0.934..., 0.937..., 0.94..., 0.941..., 0.942..., 0.943..., 0.943..., 0.944..., 0.944..., 0.945..., 0.945..., 0.946..., 0.947..., 0.949..., 0.95..., 0.951..., 0.953..., 0.954..., 0.955..., 0.957..., 0.958...

Antti Karttunen, Table of n, a(n) for n = 0..46

Cf. A213709, A071542.

(define (A226060 n) (- (A213709 (+ n 1)) (A213709 n)))

a(n) = A213709(n+1) - A213709(n).

A218599 After the first zero, integers from A213709(n)-1 to 0 followed by integers from A213709(n+1)-1 to 0, etc.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 10 2012

nonn

Antti Karttunen, Table of n, a(n) for n = 0..8727

Cf. A218601.

(define (A218599 n) (- (A218600 (A213711 n)) n))

a(n) = A218600(A213711(n))-n.

A254119 a(n) = A213709(n) - A255071(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 6, 16, 36, 71, 126, 204, 303, 414, 526, 652, 907, 1705, 4213, 11329, 29670, 73408, 171345, 379494, 802875, 1632745, 3210086, 6134908, 11457641, 21020580, 38076142

Offset: 1

Antti Karttunen, Feb 15 2015

nonn

Cf. A213709, A255071.

(define (A254119 n) (- (A213709 n) (A255071 n)))

a(n) = A213709(n) - A255071(n).

A071542 Number of steps to reach 0 starting with n and using the iterated process : x -> x - (number of 1's in binary representation of x).

Original entry on oeis.org

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

Offset: 0

Benoit Cloitre, Jun 02 2002

			17 (= 10001 in binary) -> 15 (= 1111) -> 11 (= 1011) -> 8 (= 1000) -> 7 (= 111) -> 4 (= 100) -> 3 (= 11) -> 1 -> 0, hence a(17)=8.

Antti Karttunen, Table of n, a(n) for n = 0..131072

Cf. A000120, A011371, A071542, A213706, A213707, A213708, A218254.
A179016 gives the unique infinite sequence whose successive terms are related by this iterated process (in reverse order). Also, it seems that for n>=0, a(A213708(n)) = a(A179016(n+1)) = n.
A213709(n) = a((2^(n+1))-1) - a((2^n)-1).

Table[-1 + Length@ NestWhileList[# - DigitCount[#, 2, 1] &, n, # > 0 &], {n, 0, 75}] (* Michael De Vlieger, Jul 16 2017 *)

for(n=1, 150, s=n; t=0; while(s!=0, t++; s=s-sum(i=1, length(binary(s)), component(binary(s), i))); if(s==0, print1(t, ", "); ); )

a(n)=my(k);while(n,n-=hammingweight(n);k++);k \\ Charles R Greathouse IV, Oct 30 2012
(MIT/GNU Scheme)
;; with memoizing definec-macro:
(definec (A071542 n) (if (zero? n) n (+ 1 (A071542 (- n (A000120 n)))))) ;; Antti Karttunen, Oct 24 2012

a(0)=0, a(n) = 1 + A071542(n - A000120(n)). - Antti Karttunen, Oct 24 2012

It seems that a(n) ~ C n/log(n) asymptotically with C = 1.4... (n = 10^6 gives C = 1.469..., n = 10^7 gives C = 1.4614...).

Starting offset changed to 0 with a(0) prepended as 0 by Antti Karttunen, Oct 24 2012

A255071 Number of steps required to reach (2^n)-2 from 2^(n+1)-2 by iterating the map x -> x - (number of runs in binary representation of x).

Original entry on oeis.org

1, 2, 3, 5, 9, 16, 29, 53, 97, 178, 328, 608, 1134, 2126, 4001, 7552, 14292, 27115, 51565, 98274, 187657, 358982, 687944, 1320793, 2540702, 4896919, 9456143, 18291753, 35435799, 68731296, 133436379, 259238717, 503912508, 979923792, 1906297165, 3709809375, 7222584181

Offset: 1

Antti Karttunen, Feb 14 2015

nonn

First differences of A255061 and A255062.
A255069 gives the first differences of this sequence.
Cf. A005811, A079944, A236840, A255056, A255120, A255121, A255063, A255064, A255072, A255125, A255126, A254119.
Analogous sequences: A213709, A219661.
a(n) differs from A192804(n+1) for the first time at n=11, where a(11) = 328, while A192804(12) = 327.

A005811(n) = hammingweight(bitxor(n,n\2));
A255071(n) = { my(k, i); k = (2^(n+1))-2; i = 1; while(1, k = k - A005811(k); if(!bitand(k+1,k+2),return(i),i++)); };
for(n=1, 48, write("b255071.txt", n, " ", A255071(n)));

(define (A255071 n) (- (A255072 (- (expt 2 (+ n 1)) 2)) (A255072 (- (expt 2 n) 2))))
(define (A255071shifted n) (add (COMPOSE A079944off2 A255056) (A255062 n) (A255061 (+ 1 n))))
(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n))))) ;; Cf.
A079944.
;; Shifted variant gives: (map A255071shifted (iota 16)) --> (0 1 2 3 5 9 16 29 53 97 178 328 608 1134 2126 4001)

a(n) = A255072((2^(n+1))-2) - A255072((2^n)-2).
a(n) = A255061(n+1) - A255061(n).
a(n) = A255125(n) + A255126(n).
a(n) = A255063(n) + A255064(n).
Other identities and observations:
It seems that a(n) <= A213709(n) for all n >= 1. A254119 gives the difference between these two sequences.
From Antti Karttunen, Feb 21 2015: (Start)
For n>1, a(n-1) = Sum_{k=A255062(n) .. A255061(n+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, as in the upper half of any next higher range [A255062(n+1) .. A255061(n+2)] of its infinite trunk (A255056), the beanstalk imitates its behavior in the range [A255062(n) .. A255061(n+1)].
(End)

a(37) added by Antti Karttunen, Feb 19 2015

A213710 Number of steps to reach 0 when starting from 2^n and iterating the map x -> x - (number of 1's in binary representation of x): a(n) = A071542(2^n) = A218600(n)+1.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 22, 39, 69, 123, 221, 400, 730, 1344, 2494, 4656, 8728, 16406, 30902, 58320, 110299, 209099, 397408, 757297, 1446946, 2771952, 5323983, 10250572, 19780123, 38243221, 74058514, 143592685, 278661809, 541110612, 1051158028, 2042539461, 3969857206

Offset: 0

Antti Karttunen, Oct 26 2012

nonn

Conjecture: A179016(a(n))= 2^n for all n apart from n=2. This is true if all powers of 2 except 2 itself occur in A179016 as in that case they must occur at positions given by this sequence.

This is easy to prove: It suffices to note that after 3 no integer of form (2^k)+1 can occur in A005187, thus for all k >= 2, A213725((2^k)+1) = 1 or equally: A213714((2^k)+1) = 0. - Antti Karttunen, Jun 12 2013

One more than A218600, which is the partial sums of A213709, thus the latter also gives the first differences of this sequence.
Cf. A000079, A005187, A071542, A218616, A233271.
Analogous sequences: A219665, A255062.

a(n) = A071542(A000079(n)) = A071542(2^n).

a(n) = 1 + A218600(n).

a(29)-a(36) from Alois P. Heinz, Jul 03 2022

A219661 Number of steps to go from (n+1)!-1 to n!-1 with map x -> x - (sum of digits in factorial base representation of x).

Original entry on oeis.org

1, 2, 5, 19, 83, 428, 2611, 18473, 150726, 1377548, 13851248, 152610108, 1835293041, 23925573979, 335859122743, 5049372125352, 80942722123544, 1378487515335424, 24858383452927384, 473228664468684846

Offset: 1

Antti Karttunen, Dec 03 2012

nonn

			(1!)-1 (0) is reached from (2!)-1 (1) with one step by subtracting A034968(1) from 1.
(2!)-1 (1) is reached from (3!)-1 (5) with two steps by first subtracting A034968(5) from 5 -> 2, and then subtracting A034968(2) from 2 -> 1.
(3!)-1 (5) is reached from (4!)-1 (23) with five steps by repeatedly subtracting the sum of digits in factorial expansion as: 23 - 6 = 17, 17 - 5 = 12, 12 - 2 = 10, 10 - 3 = 7, 7 - 2 = 5.
Thus a(1)=1, a(2)=2 and a(3)=5.

Hiroaki Yamanouchi, Fast Python-program for computing terms of this sequence

Row sums of A230420 and A230421.
Cf. A000142, A007623, A219651, A219652, A219662, A219663, A219665, A226061.
Cf. also A213709 (analogous sequence for base-2), A261234 (for base-3).

Table[Length@ NestWhileList[# - Total@ IntegerDigits[#, MixedRadix[Reverse@ Range[2, 120]]] &, (n + 1)! - 1, # > n! - 1 &] - 1, {n, 0, 8}] (* Michael De Vlieger, Jun 27 2016, Version 10.2 *)

(define (A219661 n) (if (zero? n) n (let loop ((i (-1+ (A000142 (1+ n)))) (steps 1)) (cond ((isA000142? (1+ (A219651 i))) steps) (else (loop (A219651 i) (1+ steps)))))))
(define (isA000142? n) (and (> n 0) (let loop ((n n) (i 2)) (cond ((= 1 n) #t) ((not (zero? (modulo n i))) #f) (else (loop (/ n i) (1+ i)))))))
;; Alternative definition:
(define (A219661 n) (- (A219652 (-1+ (A000142 (1+ n)))) (A219652 (-1+ (A000142 n)))))

a(n) = A219652((n+1)!-1) - A219652(n!-1).

a(n) = A219662(n) + A219663(n).

Terms a(16) - a(20) computed with Hiroaki Yamanouchi's Python-program by Antti Karttunen, Jun 27 2016

cp's OEIS Frontend

A218600 Partial sums of A213709.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A218602 Simple self-inverse permutation of natural numbers: after zero, list each block of A213709(n) numbers in reverse order, from A218600(n) to A213710(n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A218601 After the first zero, integers from 0 to A213709(n)-1 followed by integers from 0 to A213709(n+1)-1, etc.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A226060 First differences of A213709.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A218599 After the first zero, integers from A213709(n)-1 to 0 followed by integers from A213709(n+1)-1 to 0, etc.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A254119 a(n) = A213709(n) - A255071(n).

Views

Author

Keywords

Crossrefs

Programs

Scheme

Formula

A071542 Number of steps to reach 0 starting with n and using the iterated process : x -> x - (number of 1's in binary representation of x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A255071 Number of steps required to reach (2^n)-2 from 2^(n+1)-2 by iterating the map x -> x - (number of runs in binary representation of x).

Views

Author

Keywords

Crossrefs

Programs

PARI

Scheme

Formula

Extensions

A213710 Number of steps to reach 0 when starting from 2^n and iterating the map x -> x - (number of 1's in binary representation of x): a(n) = A071542(2^n) = A218600(n)+1.

Views

Author