cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 24 results. Next

A213709 Number of steps to go from 2^(n+1)-1 to (2^n)-1 using the iterative process described in A071542.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 17, 30, 54, 98, 179, 330, 614, 1150, 2162, 4072, 7678, 14496, 27418, 51979, 98800, 188309, 359889, 689649, 1325006, 2552031, 4926589, 9529551, 18463098, 35815293, 69534171, 135069124, 262448803, 510047416, 991381433, 1927317745, 3747885517
Offset: 0

Views

Author

Antti Karttunen, Oct 26 2012

Keywords

Comments

Also, apart from the first term a(0)=1, the number of terms in A179016 whose binary width is n+2 bits and whose second most significant bit is zero. For example, there is one term 4 (100) in three-bit range; two terms 8 (1000) and 11 (1011) in four bit range; three such terms: 16 (10000), 19 (10011) and 23 (10111) in five-bit range; five terms: 32, 35, 39, 42, 46 in six-bit range. This stems from the half-recursive nature of A179016, especially, that for all n >= 4, a(n) also gives the number of steps to go from (2^(n+1) + 2^n + 1) to 2^n using the iterative process described in A071542. Cf. also A226060. - Antti Karttunen, Jun 12 2013
Ratio a(n+1)/a(n) develops as: 1, 2, 1.5, 1.667..., 1.8, 1.889..., 1.765..., 1.8, 1.815..., 1.827..., 1.844..., 1.861..., 1.873..., 1.880..., 1.883..., 1.886..., 1.888..., 1.891..., 1.896..., 1.901..., 1.906..., 1.911..., 1.916..., 1.921..., 1.926..., 1.930..., 1.934..., 1.937..., 1.940..., 1.941..., 1.942..., 1.943..., 1.943..., 1.944..., 1.944..., 1.945..., 1.945..., 1.946..., 1.947..., 1.949..., 1.950..., 1.951..., 1.953..., 1.954..., 1.955..., 1.957..., 1.958... (which seem to converge slowly towards 2; see also comments at A218543).

Examples

			(2^0)-1 (0) is reached from (2^1)-1 (1) with one step by subtracting A000120(1) from 1.
(2^1)-1 (1) is reached from (2^2)-1 (3) with one step by subtracting A000120(3) from 3.
(2^2)-1 (3) is reached from (2^3)-1 (7) with two steps by first subtracting A000120(7) from 7 -> 4, and then subtracting A000120(4) from 4 -> 3.
Thus a(0)=a(1)=1 and a(2)=2.
		

Crossrefs

First differences of A218600 and A213710. First differences of this sequence: A226060.
Analogous sequence for factorial number system: A219661.

Formula

a(n) = A071542((2^(n+1))-1) - A071542((2^n)-1).
a(n) = A218542(n) + A218543(n) = A011782(n) - A213722(n).

Extensions

More terms from Antti Karttunen, Jun 05 2013

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

Views

Author

Antti Karttunen, Oct 26 2012

Keywords

Comments

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

Crossrefs

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

Formula

a(n) = A071542(A000079(n)) = A071542(2^n).
a(n) = 1 + A218600(n).

Extensions

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

A213708 a(n) is the least inverse of A071542, i.e., minimal i such that A071542(i) = n.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 28, 32, 34, 36, 40, 44, 48, 52, 56, 60, 64, 66, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 126, 128, 130, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 172, 176, 180, 184, 190, 192, 196, 200, 204, 208, 212, 216, 222, 226, 232, 238, 244, 250, 256, 258, 260, 264, 268, 272, 276
Offset: 0

Views

Author

Antti Karttunen, Oct 24 2012

Keywords

Comments

Also the positions in A071542 where new records appear, record values appearing in the ascending order, i.e., as A001477 (because A071542 is a monotone and surjective function).

Crossrefs

Cf. A173601 for the greatest inverse. A086876 gives the first differences.

Programs

  • Mathematica
    Function[s, Map[FirstPosition[s, #] &, Union@ s]]@ Table[-1 + Length@ NestWhileList[# - DigitCount[#, 2, 1] &, n, # > 0 &], {n, 276}] // Flatten (* Michael De Vlieger, Jul 16 2017 *)

A218542 Number of times when an even number is encountered, when going from 2^(n+1)-1 to (2^n)-1 using the iterative process described in A071542.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 8, 12, 23, 44, 86, 163, 308, 576, 1074, 1991, 3680, 6800, 12626, 23644, 44751, 85567, 164941, 319694, 621671, 1211197, 2362808, 4614173, 9018299, 17635055, 34486330, 67408501, 131642673, 256795173, 500346954, 973913365, 1894371802, 3683559071
Offset: 0

Views

Author

Antti Karttunen, Nov 02 2012

Keywords

Comments

Ratio a(n)/A213709(n) develops as: 1, 0, 0.5, 0.333..., 0.4, 0.333..., 0.471..., 0.400..., 0.426..., 0.449..., 0.480..., 0.494..., 0.502..., 0.501..., 0.497..., 0.489..., 0.479..., 0.469..., 0.461..., 0.455..., 0.453..., 0.454..., 0.458..., 0.464..., 0.469..., 0.475..., 0.480..., 0.484..., 0.488..., 0.492..., 0.496..., 0.499..., 0.502..., 0.503..., 0.505..., 0.505..., 0.505..., 0.505..., 0.505..., 0.504..., 0.504..., 0.503..., 0.503..., 0.502..., 0.502..., 0.502..., 0.503..., 0.503... (See further comments at A218543).

Examples

			(2^0)-1 (0) is reached from (2^1)-1 (1) with one step by subtracting A000120(1) from 1. Zero is an even number, so a(0)=1.
(2^1)-1 (1) is reached from (2^2)-1 (3) with one step by subtracting A000120(3) from 3. One is not an even number, so a(1)=0.
(2^2)-1 (3) is reached from (2^3)-1 (7) with two steps by first subtracting A000120(7) from 7 -> 4, and then subtracting A000120(4) from 4 -> 3. Four is an even number, but three is not, so a(2)=1.
		

Crossrefs

Cf. A219662 (analogous sequence for factorial number system).

Formula

a(n) = Sum_{i=A218600(n) .. (A218600(n+1)-1)} A213728(i).
a(n) = A213709(n) - A218543(n).

Extensions

More terms from Antti Karttunen, Jun 05 2013

A218543 Number of times when an odd number is encountered, when going from 2^(n+1)-1 to (2^n)-1 using the iterative process described in A071542.

Original entry on oeis.org

0, 1, 1, 2, 3, 6, 9, 18, 31, 54, 93, 167, 306, 574, 1088, 2081, 3998, 7696, 14792, 28335, 54049, 102742, 194948, 369955, 703335, 1340834, 2563781, 4915378, 9444799, 18180238, 35047841, 67660623, 130806130, 253252243, 491034479, 953404380, 1853513715, 3607440034
Offset: 0

Views

Author

Antti Karttunen, Nov 02 2012

Keywords

Comments

Ratio a(n)/A213709(n) develops as: 0, 1, 0.5, 0.666..., 0.6, 0.666..., 0.529..., 0.6, 0.574..., 0.551..., 0.520..., 0.506..., 0.498..., 0.499..., 0.503..., 0.511..., 0.521..., 0.531..., 0.539..., 0.545..., 0.547..., 0.546..., 0.542..., 0.536..., 0.531..., 0.525..., 0.520..., 0.516..., 0.512..., 0.508..., 0.504..., 0.501..., 0.498..., 0.497..., 0.495..., 0.495..., 0.495..., 0.495..., 0.495..., 0.496..., 0.496..., 0.497..., 0.497..., 0.498..., 0.498..., 0.498..., 0.497..., 0.497...
Ratio a(n)/A218542(n) develops as follows from n>=2 onward:
1, 2, 1.5, 2, 1.125, 1.5, 1.348..., 1.227..., 1.081..., 1.025..., 0.994..., 0.997..., 1.013..., 1.045..., 1.086..., 1.132..., 1.172..., 1.198..., 1.208..., 1.201..., 1.182..., 1.157..., 1.131..., 1.107..., 1.085..., 1.065..., 1.047..., 1.031..., 1.016..., 1.004..., 0.994..., 0.986..., 0.981..., 0.979..., 0.978..., 0.979..., 0.981..., 0.983..., 0.986..., 0.988..., 0.989..., 0.990..., 0.991..., 0.991..., 0.989..., 0.987...
Observation: A179016 seems to alternatively slightly favor the odd numbers and then again the even numbers, at least for the terms computed so far.
Please plot this sequence against A218542 in the "ratio mode" (given as a link) to see how smoothly (almost "continuously") the ratios given above develop.
What is the reason for that smoothness? (Conjecture: The distribution of "tendrils", i.e. finite subtrees in the beanstalk and its almost fractal nature? Cf: A218787.)

Examples

			(2^0)-1 (0) is reached from (2^1)-1 (1) with one step by subtracting A000120(1) from 1. Zero is not an odd number, so a(0)=0.
(2^1)-1 (1) is reached from (2^2)-1 (3) with one step by subtracting A000120(3) from 3. One is an odd number, so a(1)=1.
(2^2)-1 (3) is reached from (2^3)-1 (7) with two steps by first subtracting A000120(7) from 7 -> 4, and then subtracting A000120(4) from 4 -> 3. Four is not an odd number, but three is, so a(2)=1.
		

Crossrefs

a(n) = A213709(n)-A218542(n). Cf. A213733, A218787, A218789.
Analogous sequence for factorial number system: A219663.

Formula

a(n) = Sum_{i=A218600(n) .. (A218600(n+1)-1)} A213729(i)

A173601 Greatest inverse of A071542, i.e., a(n) = maximal i such that A071542(i) = n.

Original entry on oeis.org

0, 1, 3, 5, 7, 9, 11, 15, 17, 19, 23, 27, 31, 33, 35, 39, 43, 47, 51, 55, 59, 63, 65, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 125, 127, 129, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 183, 189, 191, 195, 199, 203, 207
Offset: 0

Views

Author

Keywords

Comments

What is s = lim sup a(n)/(n log_2(n))? A counting argument suggests s >= 1/2, and in any case s <= 1.
Essentially also the partial sums of A086876. - Antti Karttunen, Nov 10 2012 (per personal mail from Carl R. White, Nov 02 2012)

Crossrefs

See A213708 for the least inverse. A086876 gives the first differences. Also, a(n)=A213708(n)+A086876(n)-1. Cf. A071542, A179016, A218604, A218608.

Programs

  • PARI
    v=vectorsmall(10^3);v[1]=1;for(n=2,#v,v[n]=v[n-hammingweight(n)]+1); u=vector(solve(x=1,#v,x*log(x)/log(2)-#v)\1);for(i=1,#v,if(v[i]<=#u,u[v[i]]=i)); u
    
  • Scheme
    ;; With Antti Karttunen's intseq-library:
    (define A173601 (PARTIALSUMS 1 0 (compose-funs A086876 1+)))

Formula

a(n)/log_2(a(n)) < n < a(n) for n > 1.

Extensions

Changed the starting offset by prepending a(0)=0 (with the indexing of the rest of terms thus not changed) - Antti Karttunen, Nov 10 2012

A086876 Run lengths in A071542.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 4, 2, 2, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 4, 4, 4, 4, 4, 4, 6, 4, 6, 6, 6, 6, 6, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 4, 4, 4, 4, 4, 4, 6, 4, 6, 6, 6
Offset: 0

Views

Author

Ralf Stephan, Aug 21 2003

Keywords

Comments

All a(n) are even for n>1.
Although this can be viewed as a list, the indexing still starts from zero, because a(n) tells from how many starting values one can end to 0 in n steps, with the iterative process described in A071542 (if going around in 0->0 loop is disallowed). I.e., a(n) gives the number of all nodes (whether internal or leaves) in "beanstalk" (see A179016) from which the distance to the root (zero) is n.
Records occur at positions { 1,2,7,37,122,... } which correspond to run start positions { 2,4,16,126,512,... } in A071542.

Examples

			There is only one way to reach 0 in 0 steps from anywhere, and that is from 0 itself.
There is only one way to reach 0 in 1 steps from anywhere (with no 0->0 transition allowed), and that is from 1, as 1-A000120(1)=0.
There are two ways to reach 0 in 2 steps, from 2, as 2-A000120(2)=1, and 1-A000120(1)=0, and from 3, as 3-A000120(3)=1, and 1-A000120(1)=0.
Thus a(0)=a(1)=1 and a(2)=2.
		

Crossrefs

Essentially the first differences of both A173601 and A213708.

Programs

  • PARI
    e1(n)=sum(k=0, floor(log(n)/log(2)), bittest(n, k))
    f(n)=local(c); c=0; while(n, n=n-e1(n); c=c+1); c
    p=1; r=1; for(n=1, 150, c=0; while(f(r) == p, r=r+1; c=c+1); p=f(r); print1(c", "))

Extensions

Changed the starting offset by prepending a(0)=1 (with the indexing of the rest of terms thus not changed), as A071542 now contains an initial zero. - Antti Karttunen, Nov 02 2012

A213706 Partial sums of A071542.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 15, 19, 24, 29, 35, 41, 48, 55, 62, 69, 77, 85, 94, 103, 113, 123, 133, 143, 154, 165, 176, 187, 199, 211, 223, 235, 248, 261, 275, 289, 304, 319, 334, 349, 365, 381, 397, 413, 430, 447, 464, 481, 499, 517, 535, 553, 572, 591, 610, 629, 649, 669, 689, 709, 730
Offset: 0

Views

Author

Antti Karttunen, Oct 24 2012

Keywords

Crossrefs

Used to compute A213707. a(n)+1 gives the length of the n-th row in the irregular table A218254.

Formula

a(0)=0, a(n) = a(n-1)+A071542(n)

A179016 The infinite trunk of binary beanstalk: The only infinite sequence such that a(n-1) = a(n) - number of 1's in binary representation of a(n).

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 11, 15, 16, 19, 23, 26, 31, 32, 35, 39, 42, 46, 49, 53, 57, 63, 64, 67, 71, 74, 78, 81, 85, 89, 94, 97, 101, 104, 109, 112, 116, 120, 127, 128, 131, 135, 138, 142, 145, 149, 153, 158, 161, 165, 168, 173, 176, 180, 184, 190, 193, 197, 200, 205, 209
Offset: 0

Views

Author

Carl R. White, Jun 24 2010

Keywords

Comments

a(n) tells in what number we end in n steps, when we start climbing up the infinite trunk of the "binary beanstalk" from its root (zero). The name "beanstalk" is due to Antti Karttunen.
There are many finite sequences such as 0,1,2; 0,1,3,4,7,9; etc. obeying the same condition (see A218254) and as the length increases, so (necessarily) does the similarity to this infinite sequence.

Crossrefs

A subsequence of A005187, i.e., a(n) = A005187(A213715(n)). For all n,
A071542(a(n)) = n, and furthermore A213708(n) <= a(n) <= A173601(n). (Cf. A218603, A218604).
Rows of A218254, when reversed, converge towards this sequence.
Cf. A276623, A219648, A219666, A255056, A276573, A276583, A276613 for analogous constructions, and also A259934.

Programs

  • Mathematica
    TakeWhile[Reverse@ NestWhileList[# - DigitCount[#, 2, 1] &, 10^3, # > 0 &], # <= 209 &] (* Michael De Vlieger, Sep 12 2016 *)

Formula

a(0)=0, a(1)=1, and for n > 1, if n = A218600(A213711(n)) then a(n) = (2^A213711(n)) - 1, and in other cases, a(n) = a(n+1) - A213712(n+1). (This formula is based on Carl White's observation that this iterated/converging path must pass through each (2^n)-1. However, it would be very interesting to know whether the sequence admits more traditional recurrence(s), referring to previous, not to further terms in the sequence in their definition!) - Antti Karttunen, Oct 26 2012
a(n) = A218616(A218602(n)). - Antti Karttunen, Mar 04 2013
a(n) = A054429(A233271(A218602(n))). - Antti Karttunen, Dec 12 2013

Extensions

Starting offset changed from 1 to 0 by Antti Karttunen, Nov 05 2012

A055938 Integers not generated by b(n) = b(floor(n/2)) + n (complement of A005187).

Original entry on oeis.org

2, 5, 6, 9, 12, 13, 14, 17, 20, 21, 24, 27, 28, 29, 30, 33, 36, 37, 40, 43, 44, 45, 48, 51, 52, 55, 58, 59, 60, 61, 62, 65, 68, 69, 72, 75, 76, 77, 80, 83, 84, 87, 90, 91, 92, 93, 96, 99, 100, 103, 106, 107, 108, 111, 114, 115, 118, 121, 122, 123, 124, 125, 126, 129
Offset: 1

Views

Author

Alford Arnold, Jul 21 2000

Keywords

Comments

Note that the lengths of the consecutive runs in a(n) form sequence A001511.
Integers that are not a sum of distinct integers of the form 2^k-1. - Vladeta Jovovic, Jan 24 2003
Also n! never ends in this many 0's in base 2 - Carl R. White, Jan 21 2008
A079559(a(n)) = 0. - Reinhard Zumkeller, Mar 18 2009
These numbers are dead-end points when trying to apply the iterated process depicted in A071542 in reverse, i.e. these are positive integers i such that there does not exist k with A000120(i+k)=k. See also comments at A179016. - Antti Karttunen, Oct 26 2012
Conjecture: a(n)=b(n) defined as b(1)=2, for n>1, b(n+1)=b(n)+1 if n is already in the sequence, b(n+1)=b(n)+3 otherwise. If so, then see Cloitre comment in A080578. - Ralf Stephan, Dec 27 2013
Numbers n for which A257265(m) = 0. - Reinhard Zumkeller, May 06 2015. Typo corrected by Antti Karttunen, Aug 08 2015
Numbers which have a 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 28 2025

Examples

			Since A005187 begins 0 1 3 4 7 8 10 11 15 16 18 19 22 23 25 26 31... this sequence begins 2 5 6 9 12 13 14 17 20 21
		

Crossrefs

Complement of A005187. Setwise difference of A213713 and A213717.
Row 1 of arrays A257264, A256997 and also of A255557 (when prepended with 1). Equally: column 1 of A256995 and A255555.
Cf. also arrays A254105, A254107 and permutations A233276, A233278.
Left inverses: A234017, A256992.
Gives positions of zeros in A213714, A213723, A213724, A213731, A257265, positions of ones in A213725-A213727 and A256989, positions of nonzeros in A254110.
Cf. also A010061 (integers that are not a sum of distinct integers of the form 2^k+1).
Analogous sequence for factorial base number system: A219658, for Fibonacci number system: A219638, for base-3: A096346. Cf. also A136767-A136774.

Programs

  • Haskell
    a055938 n = a055938_list !! (n-1)
    a055938_list = concat $
       zipWith (\u v -> [u+1..v-1]) a005187_list $ tail a005187_list
    -- Reinhard Zumkeller, Nov 07 2011
    
  • Mathematica
    a[0] = 0; a[1] = 1; a[n_Integer] := a[Floor[n/2]] + n; b = {}; Do[ b = Append[b, a[n]], {n, 0, 105}]; c =Table[n, {n, 0, 200}]; Complement[c, b]
    (* Second program: *)
    t = Table[IntegerExponent[(2n)!, 2], {n, 0, 100}]; Complement[Range[t // Last], t] (* Jean-François Alcover, Nov 15 2016 *)
  • PARI
    L=listcreate();for(n=1,1000,for(k=2*n-hammingweight(n)+1,2*n+1-hammingweight(n+1),listput(L,k)));Vec(L) \\ Ralf Stephan, Dec 27 2013
    
  • Python
    def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
    def a043545(n):
        x=bin(n)[2:]
        return int(max(x)) - int(min(x))
    def a079559(n): return 1 if n==0 else a043545(n + 1)*a079559(n + 1 - a053644(n + 1))
    print([n for n in range(1, 201) if a079559(n)==0]) # Indranil Ghosh, Jun 11 2017, after the comment by Reinhard Zumkeller
  • Scheme
    ;; utilizing COMPLEMENT-macro from Antti Karttunen's IntSeq-library)
    (define A055938 (COMPLEMENT 1 A005187))
    ;; Antti Karttunen, Aug 08 2015
    

Formula

a(n) = A080578(n+1) - 2 = A080468(n+1) + 2*n (conjectured). - Ralf Stephan, Dec 27 2013
From Antti Karttunen, Aug 08 2015: (Start)
Other identities. For all n >= 1:
A234017(a(n)) = n.
A256992(a(n)) = n.
A257126(n) = a(n) - A005187(n).
(End)

Extensions

More terms from Robert G. Wilson v, Jul 24 2000
Showing 1-10 of 24 results. Next