A169683 -id:A169683 - cp's OEIS frontend

A354884 Numbers whose skew binary representation (A169683) is palindromic.

0, 1, 2, 4, 8, 11, 16, 26, 32, 39, 50, 57, 64, 86, 98, 120, 128, 143, 166, 181, 194, 209, 232, 247, 256, 302, 326, 372, 386, 432, 456, 502, 512, 543, 590, 621, 646, 677, 724, 755, 770, 801, 848, 879, 904, 935, 982, 1013, 1024, 1118, 1166, 1260, 1286, 1380, 1428

Offset: 1

Amiram Eldar, Jun 10 2022

The sequence of powers of 2 (A000079) is a subsequence since A169683(1) = 1, A169683(2) = 2, and for n > 2 A169683(2^n) = 10..01 with n-1 0's between the two 1's.
A000295 is a subsequence since A169683(A000295(0)) = A169683(A000295(1)) = 0 and for n>1 A169683(A000295(n)) is a repunit with n-1 1's.
A144414 is a subsequence since A169683(A144414(1)) = 1 and for n>1 A169683(A144414(n)) = 1010..01 with n-1 0's interleaved with n 1's.

			The first 10 terms are:
   n  a(n)  A169683(a(n))
  --  ----  -------------
   1    0               0
   2    1               1
   3    2               2
   4    4              11
   5    8             101
   6   11             111
   7   16            1001
   8   26            1111
   9   32           10001
  10   39           10101

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A169683.
Subsequences: A000079, A000295, A144414.
Similar sequences: A002113, A006995, A014190, A094202, A331191, A351712, A351717, A352087, A352105, A352319, A352341.

f[0] = 0; f[n_] := Module[{m = Floor@Log2[n + 1], d = n, pos}, Reap[While[m > 0, pos = 2^m - 1; Sow@Floor[d/pos]; d = Mod[d, pos]; --m;]][[2, 1]] // FromDigits]; Select[Range[0, 15000], PalindromeQ[f[#]] &] (* after N. J. A. Sloane at A169683 *)

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128

Offset: 0

N. J. A. Sloane, May 20 1991; Allan Wilks, Dec 11 1999

Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165).
Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan, Aug 27 2003
Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - Reinhard Zumkeller, Mar 18 2009
Wikipedia's article on the "Whitney Immersion theorem" mentions that the a(n)-dimensional sphere arises in the Immersion Conjecture proved by Ralph Cohen in 1985. - Jonathan Vos Post, Jan 25 2010
For n > 0, denominators for consecutive pairs of integral numerator polynomials L(n+1,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1-tx+x^2). - Tom Copeland, Feb 04 2016
a(n) is the total number of pointers in the first n elements of a perfect skip list. - Alois P. Heinz, Dec 14 2017
a(n) is the position of the n-th a (indexing from 0) in the fixed point of the morphism a -> aab, b -> b. - Jeffrey Shallit, Dec 24 2020
Numbers that can be expressed as the sum of distinct numbers of the form 2^k - 1 (lenient Mersenne numbers, A000225). This follows from the 2N - Hamming weight definition. A corollary is that these are the numbers with no 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 25 2025

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 1000 terms from T. D. Noe)
Jean-Paul Allouche, Jean Bétréma, and Jeffrey Shallit, Sur des points fixes de morphismes d'un monoïde libre, RAIRO-Theor. Inf. Appl. 23 (1989), 235-249.
Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso, Edward M. Reingold, and René Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
Barry Brent, On the Constant Terms of Certain Laurent Series, Preprints (2023) 2023061164.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Ralph L. Cohen, The Immersion Conjecture for Differentiable Manifolds, The Annals of Mathematics, 1985: 237-328.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Keith Johnson and Kira Scheibelhut, Rational Polynomials That Take Integer Values at the Fibonacci Numbers, American Mathematical Monthly 123.4 (2016): 338-346. See p. 340.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Anunay Kulshrestha, On Hamming Distance between base-n representations of whole numbers, arXiv:1203.4547 [cs.DM], 2012.
Michael E. Saks and Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383-387.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Wikipedia, Whitney Immersion Theorem.
Allan Wilks, Email to N. J. A. Sloane, Jul 7 1988.

Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161.
Cf. A001511 (first differences), A122247 (partial sums), A055938 (complement).
Cf. A004134, A010050, A000165.
Cf. A000120, A079559, A085354, A030308, A000225.

a005187 n = a005187_list !! n
a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
-- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011

[n + Valuation(Factorial(n), 2): n in [0..70]]; // Vincenzo Librandi, Jun 11 2019

A005187 := n -> 2*n - add(i, i=convert(n, base, 2)):
seq(A005187(n), n=0..65); # Peter Luschny, Apr 08 2014

a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)
Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* Robert G. Wilson v, Apr 19 2006 *)
Table[2n-DigitCount[2n,2,1],{n,0,70}] (* Harvey P. Dale, May 24 2014 *)

{a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* Michael Somos, Aug 28 2007 */

a(n)=my(s=n);while(n>>=1,s+=n);s \\ Charles R Greathouse IV, Apr 07 2012

a(n)=2*n-hammingweight(n) \\ Charles R Greathouse IV, Jan 07 2013

def A005187(n): return 2*n-bin(n).count('1') # Chai Wah Wu, Jun 03 2021

@CachedFunction
def A005187(n): return A005187(n//2) + n if n > 0 else 0
[A005187(n) for n in range(66)]  # Peter Luschny, Dec 13 2012

a(n) = A011371(2n+1) = A011371(n) + n, n >= 0.
A046161(n) = 2^a(n).
For m>0, let q = floor(log_2(m)); a(2m+1) = 2^q + 3m + Sum_{k>=1} floor((m-2^q)/2^k); a(2m) = a(2m+1) - 1. - Len Smiley
a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - Henry Bottomley, Jul 03 2001
G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - Ralf Stephan, Dec 24 2002
a(n) = Sum_{k=1..n} A001511(k), sum of binary Hamming distances between consecutive integers up to n. - Gary W. Adamson, Jun 15 2003
Conjecture: a(n) = 2n + O(log(n)). - Benoit Cloitre, Oct 07 2003 [true as a(n) = 2*n - hamming_weight(2*n). Joerg Arndt, Jun 10 2019]
Sum_{n=2^k..2^(k+1)-1} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - Philippe Deléham, Feb 19 2004
From Hieronymus Fischer, Aug 14 2007: (Start)
Recurrence: a(n) = n + a(floor(n/2)); a(2n) = 2n + a(n); a(n*2^m) = 2*n*(2^m-1) + a(n).
  a(2^m) = 2^(m+1) - 1, m >= 0.
Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= 2n-1; equality holds for powers of 2.
a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0.
lim inf (2n - a(n)) = 1, for n-->oo.
lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo.
lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End)
a(n) = 2n - A000120(n). - Paul Barry, Oct 26 2007
PURRS demo results: Bounds for a(n) = n + a(n/2) with initial conditions a(1) = 1: a(n) >= -2 + 2*n - log(n)*log(2)^(-1), a(n) <= 1 + 2*n for each n >= 1. - Alexander R. Povolotsky, Apr 06 2008
If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used to prove that 2^n maximally divides (2n!)/n!. - Jon Perry, Jul 16 2009
a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - Philippe Deléham, Oct 16 2011
a(n) = log_2(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011
a(2n+1) = a(2n) + 1. - M. F. Hasler, Jan 24 2015
a(n) = A004134(n) - n. - Cyril Damamme, Aug 04 2015
G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jul 23 2017

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

Alford Arnold, Jul 21 2000

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

			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

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.
Cf. A001511, A046699, A079559, A080578, A086343, A227359, A227408, A234016.
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.
Cf. A257508, A257509, A257126.

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

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 *)

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

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

;; utilizing COMPLEMENT-macro from Antti Karttunen's IntSeq-library)
(define A055938 (COMPLEMENT 1 A005187))
;; Antti Karttunen, Aug 08 2015

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)

More terms from Robert G. Wilson v, Jul 24 2000

A317204 Expansion of n in the p-system based on convergents to sqrt(2).

Original entry on oeis.org

0, 1, 10, 11, 20, 100, 101, 110, 111, 120, 200, 201, 1000, 1001, 1010, 1011, 1020, 1100, 1101, 1110, 1111, 1120, 1200, 1201, 2000, 2001, 2010, 2011, 2020, 10000, 10001, 10010, 10011, 10020, 10100, 10101, 10110, 10111, 10120, 10200, 10201, 11000, 11001, 11010, 11011

Offset: 0

N. J. A. Sloane, Aug 07 2018

This is the minimal (or greedy) representation of nonnegative numbers in terms of the positive Pell numbers (A000129). - Amiram Eldar, Mar 12 2022

A. F. Horadam, Zeckendorf representations of positive and negative integers by Pell numbers, Applications of Fibonacci Numbers, Springer, Dordrecht, 1993, pp. 305-316.

Amiram Eldar, Table of n, a(n) for n = 0..10000
L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Pellian Representations, The Fibonacci Quarterly, Vol. 10, No. 5 (1972), pp. 449-488.
Aviezri S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly, Vol. 89, No. 6 (1982), pp. 353-361. See Table 2.

Cf. A000129, A169683.
Similar to, but different from, A014418.
Similar sequences: A014417, A130310, A278038.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; pellp[n_] := Module[{s = {}, m = n, k}, While[m > 0, k = 1; While[pell[k] <= m, k++]; k--; AppendTo[s, k]; m -= pell[k]; k = 1]; FromDigits @ IntegerDigits[Total[3^(s - 1)], 3]]; Array[pellp, 50, 0] (* Amiram Eldar, Mar 12 2022 *)

a(n) = { my (p=[1,2]); for (k=2, oo, if (n<=p[k], my (v=0, d); while (n, v+=10^k*d=n\p[k]; n-=d*p[k]; k--); return (v/10), p = concat(p, 2*p[k]+p[k-1]))) } \\ Rémy Sigrist, Mar 12 2022

More terms from Amiram Eldar, Mar 12 2022

A215020 a(n) = log_2( A182105(n) ).

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 4, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 4, 5, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 4, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1

Offset: 1

N. J. A. Sloane, Aug 01 2012

nonn

Apparently the leftmost positions of change with incrementing skew-binary numbers (A169683), see example. - Joerg Arndt, May 27 2016

Irregular table read by rows, where the k-th row counts from 0 up to the ruler function of k, A007814(k). - Allan C. Wechsler, Sep 26 2019

			From _Joerg Arndt_, May 27 2016: (Start)
The first nonnegative skew-binary numbers (dots denote zeros) are
n :  [skew-binary]  position of change
00:  [ . . . . . ]  -
01:  [ . . . . 1 ]  0
02:  [ . . . . 2 ]  0
03:  [ . . . 1 . ]  1
04:  [ . . . 1 1 ]  0
05:  [ . . . 1 2 ]  0
06:  [ . . . 2 . ]  1
07:  [ . . 1 . . ]  2
08:  [ . . 1 . 1 ]  0
09:  [ . . 1 . 2 ]  0
10:  [ . . 1 1 . ]  1
11:  [ . . 1 1 1 ]  0
12:  [ . . 1 1 2 ]  0
13:  [ . . 1 2 . ]  1
14:  [ . . 2 . . ]  2
15:  [ . 1 . . . ]  3
16:  [ . 1 . . 1 ]  0
17:  [ . 1 . . 2 ]  0
18:  [ . 1 . 1 . ]  1
19:  [ . 1 . 1 1 ]  0
20:  [ . 1 . 1 2 ]  0
21:  [ . 1 . 2 . ]  1
22:  [ . 1 1 . . ]  2
23:  [ . 1 1 . 1 ]  0
24:  [ . 1 1 . 2 ]  0
25:  [ . 1 1 1 . ]  1
26:  [ . 1 1 1 1 ]  0
27:  [ . 1 1 1 2 ]  0
28:  [ . 1 1 2 . ]  1
29:  [ . 1 2 . . ]  2
30:  [ . 2 . . . ]  3
31:  [ 1 . . . . ]  4
32:  [ 1 . . . 1 ]  0
33:  [ 1 . . . 2 ]  0
...
(End)
From _Allan C. Wechsler_, Sep 27 2019 (Start)
First few rows of irregular table derived from A007814 (see comments).
0
0 1
0
0 1 2
0
0 1
0
0 1 2 3
0
0 1
...
(End)

Wikipedia, Skew binary number system

Cf. A182105, A082850, A007814.

a(n) = A082850(n) - 1. - Omar E. Pol, Jun 18 2019

cp's OEIS Frontend

A354047 A169683 read as ternary numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A354884 Numbers whose skew binary representation (A169683) is palindromic.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Scheme

Formula

Extensions

A317204 Expansion of n in the p-system based on convergents to sqrt(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A215020 a(n) = log_2( A182105(n) ).

Views

Author

Keywords

Comments

Examples

Links