A030308 -id:A030308 - cp's OEIS frontend

A047208 Numbers that are congruent to {0, 4} mod 5.

0, 4, 5, 9, 10, 14, 15, 19, 20, 24, 25, 29, 30, 34, 35, 39, 40, 44, 45, 49, 50, 54, 55, 59, 60, 64, 65, 69, 70, 74, 75, 79, 80, 84, 85, 89, 90, 94, 95, 99, 100, 104, 105, 109, 110, 114, 115, 119, 120, 124, 125, 129, 130, 134, 135, 139, 140, 144, 145, 149

Offset: 1

N. J. A. Sloane

Also solutions to 3^x + 5^x == 2 (mod 11). - Cino Hilliard, May 18 2003

G. C. Greubel, Table of n, a(n) for n = 1..5000
Cino Hilliard, solutions to 3^x + 5^x == 2 mod 11/, June 2003.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A001622, A010674, A010685 (first differences), A274406.

[(5*(n-1) + 3*((n-1) mod 2))/2: n in [1..100]]; // G. C. Greubel, Nov 23 2021

{#,#+4}&/@(5*Range[0,30])//Flatten (* Harvey P. Dale, Apr 05 2019 *)

forstep(n=0,200,[4,1],print1(n", ")) \\ Charles R Greathouse IV, Oct 17 2011

[(5*(n-1) +3*((n-1)%2))/2 for n in (1..100)] # G. C. Greubel, Nov 23 2021

From R. J. Mathar, Jan 24 2009: (Start)
G.f.: x^2*(4+x)/((1-x)^2*(1+x)).
a(n) = a(n-2) + 5. (End)
a(n) = 5*n - 6 - a(n-1) (with a(1)=0). - Vincenzo Librandi, Nov 18 2010
a(n+1) = Sum_{k>=0} A030308(n,k)*b(k), with b(0)=4 and b(k) = A020714(k-1) = 5*2^(k-1) for k>0. - Philippe Deléham, Oct 17 2011
a(n) = ceiling((5/3)*ceiling(3*n/2)). - Clark Kimberling, Jul 04 2012
a(n) = (5*(n-1) + 3*(n-1 mod 2))/2 = (5*(n-1) + A010674(n-1))/2. - G. C. Greubel, Nov 23 2021
Sum_{n>=2} (-1)^n/a(n) = log(5)/4 + log(phi)/(2*sqrt(5)) - sqrt(1+2/sqrt(5))*Pi/10, where phi is the golden ratio (A001622). - Amiram Eldar, Dec 07 2021
E.g.f.: 1 + ((5*x - 7/2)*exp(x) + (3/2)*exp(-x))/2. - David Lovler, Aug 23 2022

A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result.

Original entry on oeis.org

3, 12, 7, 24, 51, 28, 15, 48, 99, 204, 103, 56, 115, 60, 31, 96, 195, 396, 199, 408, 819, 412, 207, 112, 227, 460, 231, 120, 243, 124, 63, 192, 387, 780, 391, 792, 1587, 796, 399, 816, 1635, 3276, 1639, 824, 1651, 828, 415, 224, 451, 908, 455, 920, 1843, 924

Offset: 1

Leroy Quet, Dec 02 2009

A318921 expands the runs in a similar way, and A318921(a(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018
From Chai Wah Wu, Nov 18 2018: (Start)
Let f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e., the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 3 and f(1) = a(2) + a(3) = 19.
Then f(k) = 20*6^(k-1) - 2^(k-1) for k > 0.
Proof: by summing over the recurrence relations for a(n) (see formula section), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (6*a(2i) + 6*a(2i+1) + 4) = 6*f(k+1) + 2^(k+2). Solving this first-order recurrence relation with the initial condition f(1) = 19 shows that f(k) = 20*6^(k-1)-2^(k-1) for k > 0.
(End)

			6 in binary is 110. Increase each run by one digit to get 11100, which is 28 in decimal. So a(6) = 28.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.

Cf. A175047, A175048, A324127 (partial sums).
Cf. also A030308, A007088, A182512, A318921.
For records see A319422, A319423, A319424.

import Data.List (group)
a175046 = foldr (\b v -> 2 * v + b) 0 .
          concatMap (\bs@(b:_) -> b : bs) . group . a030308_row
-- Reinhard Zumkeller, Jul 05 2013

a[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;
Array[a, 60] (* Jean-François Alcover, Nov 12 2018 *)

A175046(n)={for(i=2,#n=binary (n*2+bittest (n,0)),n[i]!=n[i-1]&&n[i-1]*=[1,1]);fromdigits(concat(n),2)} \\ M. F. Hasler, Sep 08 2018

from re import split
def A175046(n):
    return int(''.join(d+'1' if '1' in d else d+'0' for d in split('(0+)|(1+)',bin(n)[2:]) if d != '' and d != None),2) # Chai Wah Wu, Sep 24 2018

def a(n):
    b = bin(n)[2:]
    return int(b.replace("01", "001").replace("10", "110") + b[-1], 2)
print([a(n) for n in range(1, 55)]) # Michael S. Branicky, Dec 07 2021

2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2). - M. F. Hasler, Sep 08 2018
a(n) <= (9*n^2 + 12*n)/5, with equality iff n = (2/3)*(4^k-1) = A182512(k) for some k, i.e., n = 10101...10 in binary. - Conjectured by N. J. A. Sloane, Sep 09 2018, proved by M. F. Hasler, Sep 12 2018
From M. F. Hasler, Sep 12 2018: (Start)
Proof of N. J. A. Sloane's formula: For given (binary) length L(n) = floor(log_2(n)+1), the length of a(n) is maximal, L(a(n)) = 2*L(n), if and only if n's bits are alternating, i.e., n in A020988 (if even) or in A002450 (if odd).
For n = A020988(k) (= k times '10' in base 2) = (4^k - 1)*2/3, one has a(n) = A108020(k) (= k times '1100' in base 2) = (16^k - 1)*4/5. This yields a(n)/n = (4^k + 1)*6/5 = (n*9 + 12)/5, i.e., the given upper bound.
For n = A002450(k) = (4^k - 1)/3, one gets a(n) = A182512(k) = (16^k - 1)/5, whence a(n)/n = (4^k + 1)*3/5 = (n*9 + 6)/5, smaller than the bound.
If L(a(n)) < 2 L(n) - 1, then log_2(a(n)) < floor(log_2(a(n))+1) = L(a(n)) <= 2*L(n) - 2 = 2*floor(log_2(n)+1)-2 = 2*floor(log_2(n)) <= 2*log_2(n), whence a(n) < n^2.
It remains to consider the case L(a(n)) = 2 L(n) - 1. There are two possibilities:
If n = 10..._2, then n >= 2^(L(n)-1) and a(n) = 1100..._2 < 1101_2 * 2^(L(a(n))-4) = 13*2^(2*L(n)-5), so a(n)/n^2 < 13*2^(-5+2) = 13/8 = 1.625 < 9/5 = 1.8.
If n = 11..._2, then n >= 3*2^(L(n)-2) and a(n) = 111..._2 < 2^L(a(n)) = 2^(2*L(n)-1), so a(n)/n^2 < 2^(-1+4)/9 = 8/9 < 1 < 9/5.
This shows that a(n)/n^2 <= 9/5 + 12/(5*n) always holds, with equality iff n is in A020988; and a(n)/n^2 < 13/8 if n is not in A020988 or A002450. (End)
From M. F. Hasler, Sep 10 2018: (Start)
Right inverse of A318921: A318921 o A175046 = id (= A001477).
a(A020988(k)) = A108020(k); a(A002450(k)) = A182512(k); a(A000225(k)) = A000225(k+1) (achieves the lower bound a(n) >= 2n + 1) for all k >= 0. (End)
From David A. Corneth, Sep 20 2018: (Start)
a(4*k)   = 2*a(2*k).
a(4*k+1) = 4*a(2*k) + 3.
a(4*k+2) = 4*a(2*k+1).
a(4*k+3) = 2*a(2*k+1) + 1. (End)

Extended by Ray Chandler, Dec 18 2009

A059906 Index of second half of decomposition of integers into pairs based on A000695.

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6

Offset: 0

Marc LeBrun, Feb 07 2001

One coordinate of a recursive non-self-intersecting walk on the square lattice Z^2.

			A000695(A059905(14)) + 2*A000695(a(14)) = A000695(2) + 2*A000695(3) = 4 + 2*5 = 14.
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = b_1 + b_3*2 = 3. - _Vladimir Shevelev_, Nov 13 2008

Rémy Sigrist, Table of n, a(n) for n = 0..8192
G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966, with a(n) being section 5.1 step (b).
Index entries for sequences related to coordinates of 2D curves

Cf. A000695, A057300, A059905.

a[n_] := Module[{P}, (P = Partition[IntegerDigits[n, 2]//Reverse, 2][[All, 2]]).(2^(Range[Length[P]]-1))]; Array[a, 105, 0] (* Jean-François Alcover, Apr 24 2019 *)

A059906(n) = { my(t=1,s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

def a(n):
    x=[int(t) for t in list(bin(n)[2:])[::-1]]
    return sum(x[2*i + 1]*2**i for i in range(int(len(x)//2)))
print([a(n) for n in range(105)]) # Indranil Ghosh, Jun 25 2017

def A059906(n): return 0 if n < 2 else int(bin(n)[-2:1:-2][::-1],2) # Chai Wah Wu, Jun 30 2022

n = A000695(A059905(n)) + 2*A000695(a(n))
To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 13 2008
a(n) = Sum_{k>=0} A030308(n,k)*b(k) with b(0)=0 and b(k)=A077957(k-1) for k>0. - Philippe Deléham, Oct 18 2011
Conjecture: a(n) = n - (1/2)*Sum_{k=1..n} (sqrt(2)^A007814(k) + (-sqrt(2))^A007814(k)) = -Sum_{k=1..n} (-1)^k * 2^floor(k/2) * floor(n/2^k). - Velin Yanev, Dec 01 2016

A031235 Triangle T(n,k): write n in base 5, reverse order of digits.

Original entry on oeis.org

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

Offset: 0

Clark Kimberling

Reinhard Zumkeller, Rows n = 0..1000 of triangle, flattened

Cf. A030308, A030341, A030386, A030567, A031007, A031045, A031087, A031298 for the base-2 to base-10 analogs.

Cf. A007091.

a031235 n k = a031235_tabf !! n !! k
a031235_row n = a031235_tabf !! n
a031235_tabf = iterate succ [0] where
   succ []     = [1]
   succ (4:ts) = 0 : succ ts
   succ (t:ts) = (t + 1) : ts
-- Reinhard Zumkeller, Sep 18 2015

Reverse[IntegerDigits[#,5]]&/@Range[0,40]//Flatten (* Harvey P. Dale, Aug 02 2016 *)

A031235(n, k=-1)=/*k<0&&error("Flattened sequence not yet implemented.")*/n\5^k%5 \\ Assuming that columns are numbered starting with k=0 as in A030308, A030341, ... - M. F. Hasler, Jul 21 2013

Initial 0 and better name by Philippe Deléham, Oct 20 2011

A001068 a(n) = floor(5*n/4), numbers that are congruent to {0, 1, 2, 3} mod 5.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 46, 47, 48, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 85, 86, 87, 88

Offset: 0

N. J. A. Sloane

From M. F. Hasler, Oct 21 2008: (Start)
Also, for n>0, the 4th term (after [0,n,3n]) in the continued fraction expansion of arctan(1/n). (Observation by V. Reshetnikov)
Proof:
arctan(1/n) = (1/n) / (1 + (1/n)^2/( 3 + (2/n)^2/( 5 + (3/n)^2/( 7 + ...)...)
            = 1 / ( n + 1/( 3n + 4/( 5n + 9/( 7n + 25/(...)...)
            = 1 / ( n + 1/( 3n + 1/( 5n/4 + (9/4)/( 7n + 25/(...)...),
and the term added to 5n/4, (9/4)/(7n+...) = (1/4)*9/(7n+...) is less than 1/4 for all n>=2. (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Paul Erdős, Some recent problems and results in graph theory, Discr. Math., Vol. 164, No. 1-3 (1997), pp. 81-85.
Wikipedia, Continued fraction for arctangent.
R. Witula, P. Lorenc, M. Rozanski and M. Szweda, Sums of the rational powers of roots of cubic polynomials, Zeszyty Naukowe Politechniki Slaskiej, Seria: Matematyka Stosowana z. 4, Nr. kol. 1920, (2014), pp. 17-34.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Cf. A001622, A002265, A030308, A047203, A110255, A110256, A110257, A110258, A110259, A110260, A177704 (first differences), A249547.

[Floor(5*n/4): n in [0..80]]; // Vincenzo Librandi, Nov 13 2011

A001068:=n->floor(5*n/4); seq(A001068(k), k=0..100); # Wesley Ivan Hurt, Nov 07 2013

Table[Floor[5*n/4],{n,0,120}] (* Vladimir Joseph Stephan Orlovsky, Jan 28 2012 *)
#+{0,1,2,3}&/@(5*Range[0,20])//Flatten (* or *) Complement[Range[0,103],5*Range[20]-1] (* Harvey P. Dale, Dec 03 2023 *)

a(n)=5*n\4 /* or, cf. comment: */
a(n)=contfrac(atan(1/n))[4] \\ M. F. Hasler, Oct 21 2008

contfrac( arctan( 1/n )) = 0 + 1/( n + 1/( 3n + 1/( a(n) + 1/(...)))). - M. F. Hasler, Oct 21 2008
a(n) = Sum_{k>=0} A030308(n,k)*b(k) with b(0)=1, b(1)=2 and b(k)=5*2^(k-2) for k>1. - Philippe Deléham, Oct 17 2011.
From Bruno Berselli, Oct 17 2011:  (Start)
G.f.: x*(1+x+x^2+2*x^3)/((1+x)*(1-x)^2*(1+x^2)).
a(n) = (10*n+2*(-1)^((n-1)n/2)+(-1)^n-3)/8.
a(-n) = -A047203(n+1). (End)
From Wesley Ivan Hurt, Sep 17 2015: (Start)
a(n) = a(n-1) + a(n-4) - a(n-5) for n>4.
a(n) = n + floor(n/4). (End)
a(n) = n + A002265(n). - Robert Israel, Sep 17 2015
E.g.f.: (sin(x) + cos(x) + (5*x - 2)*sinh(x) + (5*x - 1)*cosh(x))/4. - Ilya Gutkovskiy, May 06 2016
Sum_{n>=1} (-1)^(n+1)/a(n) = log(5)/4 + sqrt(5)*log(phi)/10 + sqrt(5-2*sqrt(5))*Pi/10, where phi is the golden ratio (A001622). - Amiram Eldar, Dec 10 2021

More terms from James Sellers, Sep 19 2000

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285

Offset: 1

N. J. A. Sloane

Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.
Piecewise linear: breakpoints at powers of 2 with values given by A000337.
a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer, Dec 05 2006
It is also coincidentally the maximum number of comparisons for merge sort. - Li-yao Xia, Nov 18 2015

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal layered permutations, arXiv:1710.04240 [math.CO], (2017).
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal Layered Permutations, Electronic Journal of Combinatorics. Volume 25(3), 2018, #P3.23.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
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
Hsien-Kuei Hwang, S. Janson, and T.-H. 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, S. Janson, and T.-H. 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.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
D. Knuth, Letter to N. J. A. Sloane, date unknown
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Sorting.
Index entries for sequences related to sorting

Partial sums of A029837.

Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.

import Data.List (transpose)
a001855 n = a001855_list !! n
a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

a := proc(n) local k; k := ilog2(n) + 1; 1 + n*k - 2^k end; # N. J. A. Sloane, Dec 01 2007 [edited by Peter Luschny, Nov 30 2017]

a[n_?EvenQ] := a[n] = n + 2a[n/2] - 1; a[n_?OddQ] := a[n] = n + a[(n+1)/2] + a[(n-1)/2] - 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Nov 23 2011, after Pari *)
a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;
Table[a[n], {n, 1, 58}] (* Peter Luschny, Dec 02 2017 *)
Accumulate[BitLength[Range[0, 100]]] (* Paolo Xausa, Sep 30 2024 *)

PARI
```
a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)

def A001855(n):
    s, i, z = 0, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A001855(n) for n in range(1, 59)]) # Peter Luschny, Nov 30 2017

def A001855(n): return n*(m:=(n-1).bit_length())-(1<Chai Wah Wu, Mar 29 2023

Let n = 2^(k-1) + g, 0 <= g <= 2^(k-1); then a(n) = 1 + n*k - 2^k. - N. J. A. Sloane, Dec 01 2007
a(n) = Sum_{k=1..n}ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.
a(n) = a(floor(n/2)) + a(ceiling(n/2)) + n - 1.
G.f.: x/(1-x)^2 * Sum_{k>=0} x^2^k. - Ralf Stephan, Apr 13 2002
a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - Benoit Cloitre, Apr 26 2003
a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta Jovovic, Aug 15 2004
a(n) = A061168(n-1) + n - 1 for n>1. - Hieronymus Fischer, Dec 05 2006
a(n) = A123753(n-1) - n. - Peter Luschny, Nov 30 2017

Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)

A372433 Binary weight (number of ones in binary expansion) of the n-th squarefree number.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 5, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 3, 4, 4, 4, 5, 4, 5, 5, 5, 6, 3, 4, 4, 5, 4, 4, 5, 5, 5, 6, 4, 4, 5, 5, 6, 5, 6, 7, 2, 2, 3, 3, 3, 3, 3, 4, 4

Offset: 1

Gus Wiseman, May 04 2024

Harvey P. Dale, Table of n, a(n) for n = 1..1000
MathOverflow, Are there primes of every Hamming weight?
Wikipedia, Hamming weight.

Restriction of A000120 to A005117.
For prime instead of squarefree we have A014499, zeros A035103.
Counting zeros instead of ones gives A372472, cf. A023416, A372473.
For binary length instead of weight we have A372475.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A145037 counts ones minus zeros in binary expansion, cf. A031443, A031444, A031448, A097110.
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
A372516 counts ones minus zeros in binary expansion of primes, cf. A177718, A177796, A372538, A372539.
Cf. A039004, A049093, A049094, A059015, A069010, A070939, A073642, A211997, A368494, A372474.

DigitCount[Select[Range[100],SquareFreeQ],2,1]
Total[IntegerDigits[#,2]]&/@Select[Range[200],SquareFreeQ] (* Harvey P. Dale, Feb 14 2025 *)

from math import isqrt
from sympy import mobius
def A372433(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m).bit_count() # Chai Wah Wu, Aug 02 2024

a(n) = A000120(A005117(n)).

a(n) + A372472(n) = A372475(n) = A070939(A005117(n)).

A030386 Triangle T(n,k): write n in base 4, reverse order of digits.

Original entry on oeis.org

0, 1, 2, 3, 0, 1, 1, 1, 2, 1, 3, 1, 0, 2, 1, 2, 2, 2, 3, 2, 0, 3, 1, 3, 2, 3, 3, 3, 0, 0, 1, 1, 0, 1, 2, 0, 1, 3, 0, 1, 0, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 0, 2, 1, 1, 2, 1, 2, 2, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 2, 3, 1, 3, 3, 1, 0, 0, 2, 1, 0, 2, 2, 0, 2, 3, 0, 2, 0, 1, 2

Offset: 0

Clark Kimberling

			Triangle begins:
0
1
2
3
0, 1
1, 1
2, 1
3, 1
0, 2
1, 2
2, 2
3, 2
0, 3
1, 3
2, 3
3, 3
0, 0, 1
1, 0, 1 ... - _Philippe Deléham_, Oct 20 2011

Reinhard Zumkeller, Rows n = 0..1000 of triangle, flattened

Cf. A030308, A030341, A031235, A030567, A031007, A031045, A031087, A031298 for the base-2 to base-10 analogs.

Cf. A007090.

a030386 n k = a030386_tabf !! n !! k
a030386_row n = a030386_tabf !! n
a030386_tabf = iterate succ [0] where
   succ []     = [1]
   succ (3:ts) = 0 : succ ts
   succ (t:ts) = (t + 1) : ts
-- Reinhard Zumkeller, Sep 18 2015

A030386_row := n -> op(convert(n, base, 4)):
seq(A030386_row(n), n=0..36); # Peter Luschny, Nov 28 2017

Flatten[Table[Reverse[IntegerDigits[n,4]],{n,0,50}]] (* Harvey P. Dale, Oct 13 2012 *)

A030386(n, k=-1)=/*k<0&&error("Flattened sequence not yet implemented.")*/n\4^k%4 \\ Assuming that columns are numbered starting with k=0 as in A030308, A030341, ... \\ M. F. Hasler, Jul 21 2013

Initial 0 and better name by Philippe Deléham, Oct 20 2011

A053985 Replace 2^k with (-2)^k in binary expansion of n.

Original entry on oeis.org

0, 1, -2, -1, 4, 5, 2, 3, -8, -7, -10, -9, -4, -3, -6, -5, 16, 17, 14, 15, 20, 21, 18, 19, 8, 9, 6, 7, 12, 13, 10, 11, -32, -31, -34, -33, -28, -27, -30, -29, -40, -39, -42, -41, -36, -35, -38, -37, -16, -15, -18, -17, -12, -11, -14, -13, -24, -23, -26, -25, -20, -19

Offset: 0

Henry Bottomley, Apr 03 2000

Base 2 representation for n (in lexicographic order) converted from base -2 to base 10.
Maps natural numbers uniquely onto integers; within each group of positive values, maximum is in A002450; a(n)=n iff n can be written only with 1's and 0's in base 4 (A000695).
a(n) = A004514(n) - n. - Reinhard Zumkeller, Dec 27 2003
Schroeppel gives formula n = (a(n) + b) XOR b where b = binary ...101010, and notes this formula is reversible.  The reverse a(n) = (n XOR b) - b is a bit twiddle to transform 1 bits to -1.  Odd position 0 or 1 in n is flipped by "XOR b" to 1 or 0, then "- b" gives 0 or -1.  Only odd position 1's are changed, so b can be any length sure to cover those. - Kevin Ryde, Jun 26 2020

			a(9)=-7 because 9 is written 1001 base 2 and (-2)^3 + (-2)^0 = -8 + 1 = -7.
Or by Schroeppel's formula, b = binary 1010 then a(9) = (1001 XOR 1010) - 1010 = decimal -7. - _Kevin Ryde_, Jun 26 2020

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972, item 128 by Schroeppel, page 62. Also HTML transcription. Figure 7 path drawn 0, 1, -2, -1, 4, ... is the present sequence.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 45, 49.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Inverse of A005351. Cf. A039724, A007088, A065369, A073791, A073792, A073793, A073794, A073795, A073796 and A073835.

f[n_Integer, b_Integer] := Block[{l = IntegerDigits[n]}, Sum[l[[ -i]]*(-b)^(i - 1), {i, 1, Length[l]}]]; a = Table[ FromDigits[ IntegerDigits[n, 2]], {n, 0, 80}]; b = {}; Do[b = Append[b, f[a[[n]], 2]], {n, 1, 80}]; b
(* Second program: *)
Array[FromDigits[IntegerDigits[#, 2], -2] &, 62, 0] (* Michael De Vlieger, Jun 27 2020 *)

a(n) = fromdigits(binary(n), -2) \\ Rémy Sigrist, Sep 01 2018

def A053985(n): return  -(b:=int('10'*(n.bit_length()+1>>1),2)) + (n^b) if n else 0 # Chai Wah Wu, Nov 18 2022

From Ralf Stephan, Jun 13 2003: (Start)
G.f.: (1/(1-x)) * Sum_{k>=0} (-2)^k*x^2^k/(1+x^2^k).
a(0) = 0, a(2*n) = -2*a(n), a(2*n+1) = -2*a(n)+1. (End)
a(n) = Sum_{k>=0} A030308(n,k)*A122803(k). - Philippe Deléham, Oct 15 2011
a(n) = (n XOR b) - b where b = binary ..101010 [Schroeppel].  Any b of this form (A020988) with bitlength(b) >= bitlength(n) suits. - Kevin Ryde, Jun 26 2020

cp's OEIS Frontend

A059905 Index of first half of decomposition of integers into pairs based on A000695.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Ruby

Formula

A047208 Numbers that are congruent to {0, 4} mod 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

A059906 Index of second half of decomposition of integers into pairs based on A000695.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A031235 Triangle T(n,k): write n in base 5, reverse order of digits.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A001068 a(n) = floor(5*n/4), numbers that are congruent to {0, 1, 2, 3} mod 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma