A011371 -id:A011371 - cp's OEIS frontend

A317934 Multiplicative with a(p^n) = 2^A011371(n); denominators for certain "Dirichlet Square Roots" sequences.

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 8, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 8, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 8, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 16, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 2, 2, 1, 1, 1, 8, 8, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 8, 1, 2, 2, 4, 1, 1, 1, 2, 1

Offset: 1

Antti Karttunen, Aug 12 2018

a(n) is the denominator of certain rational valued sequences f(n), that have been defined as f(n) = (1/2) * (b(n) - Sum_{d|n, d>1, dA034444 and A037445.
Many of the same observations as given in A046644 apply also here. Note that A011371 shares with A005187 the property that A011371(x+y) <= A011371(x) + A011371(y), with equivalence attained only when A004198(x,y) = 0, and also the property that A011371(2^(k+1)) = 1 + 2*A011371(2^k).
The following list gives such pairs num(n), b(n) for which b(n) is Dirichlet convolution of num(n)/a(n).
  Numerators   Dirichlet convolution of numerator(n)/a(n) yields
  -------      -----------
  A317933      A034444
  A317941      A037445
  A317940      A046644
Expansion of Dirichlet g.f. Product_{prime} 1/(1 - 2/p^s)^(1/2) is A046643/A317934. - Vaclav Kotesovec, May 08 2025

Antti Karttunen, Table of n, a(n) for n = 1..65537
Vaclav Kotesovec, Graph - the asymptotic ratio (1000000 terms)
Wikipedia, Dirichlet convolution

Cf. A011371, A034444, A317940, A317941, A317946.
Cf. A317933, A317940, A317941 (numerator-sequences).
Cf. also A046644, A299150, A299152, A317832, A317932, A317926 (for denominator sequences of other similar constructions).
Cf. A046643, A167864, A347195.

A011371(n) = (n - hammingweight(n));
A317934(n) = factorback(apply(e -> 2^A011371(e),factor(n)[,2]));

for(n=1, 100, print1(denominator(direuler(p=2, n, 1/(1-2*X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 07 2025

for(n=1, 100, print1(denominator(direuler(p=2, n, ((1+X)/(1-X))^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 09 2025

a(n) = 2^A317946(n).
a(n) = denominator of f(n), where f(1) = 1, f(n) = (1/2) * (b(n) - Sum_{d|n, d>1, d 1, where b is A034444, A037445 or A046644 for example.
Sum_{k=1..n} A046643(k)/a(k) ~ n * sqrt(A167864*log(n)/(Pi*log(2))) * (1 + (4*(gamma - 1) + 5*log(2) - 4*A347195)/(8*log(n))), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, May 08 2025

A257264 Square array A(row,col) read by antidiagonals: A(1,col) = A055938(col), and for row > 1, A(row,col) = A011371(A(row-1,col)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 03 2015

The array is read by antidiagonals: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.
Column n gives the trajectory of iterates of A011371, when starting from A055938(n), thus stepping through successive parent-nodes when starting from the n-th leaf of binary beanstalk, until finally reaching the fixed point 0, which is the root of the whole binary tree.
The hanging tails of columns (upward from the first encountered zero) converge towards A179016.

			The top left corner of the array:
2, 5, 6, 9, 12, 13, 14, 17, 20, 21, 24, 27, 28, 29, 30, 33, 36, 37, 40, 43
1, 3, 4, 7, 10, 10, 11, 15, 18, 18, 22, 23, 25, 25, 26, 31, 34, 34, 38, 39
0, 1, 3, 4,  8,  8,  8, 11, 16, 16, 19, 19, 22, 22, 23, 26, 32, 32, 35, 35
0, 0, 1, 3,  7,  7,  7,  8, 15, 15, 16, 16, 19, 19, 19, 23, 31, 31, 32, 32
0, 0, 0, 1,  4,  4,  4,  7, 11, 11, 15, 15, 16, 16, 16, 19, 26, 26, 31, 31
0, 0, 0, 0,  3,  3,  3,  4,  8,  8, 11, 11, 15, 15, 15, 16, 23, 23, 26, 26
0, 0, 0, 0,  1,  1,  1,  3,  7,  7,  8,  8, 11, 11, 11, 15, 19, 19, 23, 23
0, 0, 0, 0,  0,  0,  0,  1,  4,  4,  7,  7,  8,  8,  8, 11, 16, 16, 19, 19
0, 0, 0, 0,  0,  0,  0,  0,  3,  3,  4,  4,  7,  7,  7,  8, 15, 15, 16, 16
0, 0, 0, 0,  0,  0,  0,  0,  1,  1,  3,  3,  4,  4,  4,  7, 11, 11, 15, 15
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  1,  1,  3,  3,  3,  4,  8,  8, 11, 11
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  3,  7,  7,  8,  8
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  4,  4,  7,  7
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  3,  3,  4,  4
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  3,  3
0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1
...

Row 1: A055938, Row 2: A257507.
Cf. A011371, A055938.
Cf. also A071542, A179016, A218254, A256993, A256997, A257265.

(define (A257264 n) (A257264bi (A002260 n) (A004736 n)))
(define (A257264bi row col) (if (= 1 row) (A055938 col) (A011371 (A257264bi (- row 1) col))))

A174605 Partial sums of A011371.

Original entry on oeis.org

0, 0, 1, 2, 5, 8, 12, 16, 23, 30, 38, 46, 56, 66, 77, 88, 103, 118, 134, 150, 168, 186, 205, 224, 246, 268, 291, 314, 339, 364, 390, 416, 447, 478, 510, 542, 576, 610, 645, 680, 718, 756, 795, 834, 875, 916, 958, 1000, 1046, 1092, 1139, 1186, 1235, 1284, 1334

Offset: 0

Jonathan Vos Post, Mar 23 2010

Exponent of 2 in the superfactorials, i.e., a(n) = A007814(A000178(n)). - Ralf Stephan, Jan 03 2014

Amiram Eldar, Table of n, a(n) for n = 0..10000
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. Also first authors' copy, 2016.
Jeffrey C. Lagarias and Harsh Mehta, Products of Binomial Coefficients and Unreduced Farey Fractions, arXiv:1409.4145 [math.NT], 2014, see a(n) = ord_p(N*_n) for p=2 in theorem 4.1.
A. Mir, F. Rossello and L. Rotger, A new balance index for phylogenetic trees, arXiv preprint arXiv:1202.1223 [q-bio.PE], 2012, see proposition 15, a(n) = x(n) = f(n+1).

Cf. A000120, A011371 (first differences).
Cf. A000178 (superfactorials), A007814 (2-adic valuation), A272011 (binary exponents).
Cf. A249152 (hyperfactorial valuation), A187059 (binomial valuation), A173345 (superfactorial 10-valuation).

a:= proc(n) option remember; `if`(n<1, 0,
      a(n-1)+n-add(i, i=Bits[Split](n)))
    end:
seq(a(n), n=0..54);  # Alois P. Heinz, Oct 30 2021

Accumulate[Table[n-DigitCount[n,2,1],{n,0,130}]] (* Harvey P. Dale, Feb 26 2015 *)
a[n_] := IntegerExponent[BarnesG[n + 2], 2]; Array[a, 100, 0] (* Amiram Eldar, Aug 08 2024 *)

a(n) = n++; my(v=binary(n),t=#v-1); for(i=1,#v, if(v[i],v[i]=t++,t--)); (n^2 - fromdigits(v,2))>>1; \\ Kevin Ryde, Oct 29 2021

def A174605(n): return (n*(n+1)>>1)-(n+1)*n.bit_count()-(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1)  # Chai Wah Wu, Nov 12 2024

a(n) = Sum_{i=0..n} A011371(i).
From Kevin Ryde, Oct 29 2021: (Start)
a(n) = n*(n+1)/2 - A000788(n).
a(n) ~ (n^2)/2 + O(n*log_2(n)). [Lagarias and Mehta, theorem 4.2 with p=2]
a(n) = ( (n+1)^2 - Sum_{i=1..k} (e[i]+2*i-1) * 2^e[i] )/2, where binary expansion n+1 = 2^e[1] + ... + 2^e[k] with descending exponents e[1] > e[2] > ... > e[k] (A272011).
(End)

A257507 Row 2 of A257264: a(n) = A011371(A055938(n)).

Original entry on oeis.org

1, 3, 4, 7, 10, 10, 11, 15, 18, 18, 22, 23, 25, 25, 26, 31, 34, 34, 38, 39, 41, 41, 46, 47, 49, 50, 54, 54, 56, 56, 57, 63, 66, 66, 70, 71, 73, 73, 78, 79, 81, 82, 86, 86, 88, 88, 94, 95, 97, 98, 102, 102, 104, 105, 110, 110, 113, 116, 117, 117, 119, 119, 120, 127, 130, 130, 134, 135, 137, 137, 142, 143, 145, 146

Offset: 1

Antti Karttunen, May 03 2015

nonn

The sequence gives the parent node of each leaf-vertex (A055938) in binary beanstalk.

			Terms of A055938 are the leaf-nodes in Paul Tek's illustration. This sequence gives the corresponding parent-node (in that illustration a node immediately below where the arrow points), for each term of A055938[1..]: 2, 5, 6, 9, 12, 13, 14, ...
As A055938(4) = 9, and 9's parent node is 7 (because A011371(9) = 7), a(4) = 7.
As A055938(5) = 12, and 12's parent node is 10, a(5) = 10.
As A055938(6) = 13, and 13's parent node is 10, a(6) = 10.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Paul Tek, Illustration of how natural numbers in range 0 .. 133 are organized as a binary tree in the binary beanstalk

Row 2 of A257264.
Cf. A011371, A055938.
Cf. A257508 (same sequence with duplicates removed), A257512 (the terms which occur twice).

(define (A257507 n) (A011371 (A055938 n)))

a(n) = A011371(A055938(n)).

A297117 Möbius transform of A011371, n minus (number of 1's in binary expansion of n).

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 4, 4, 6, 4, 8, 4, 10, 6, 7, 8, 15, 6, 16, 8, 13, 10, 19, 8, 19, 12, 16, 12, 25, 8, 26, 16, 22, 16, 25, 12, 34, 18, 24, 16, 38, 12, 39, 20, 24, 22, 42, 16, 42, 20, 31, 24, 49, 18, 39, 24, 36, 28, 54, 16, 56, 30, 33, 32, 50, 20, 64, 32, 46, 24, 67, 24, 70, 36, 41, 36, 61, 24, 74, 32, 55, 40, 79, 24

Offset: 1

Antti Karttunen, Dec 26 2017

nonn

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

Cf. A000010, A000120, A008683, A011371, A051953, A297111, A297114, A297115.

A297117(n) = sumdiv(n,d,moebius(n/d)*(d-hammingweight(d)));

a(n) = Sum_{d|n} A008683(n/d) * (d - A000120(d)).
a(n) = A297111(n) - A000010(n).
a(n) = A297114(n) + A051953(n).

A317946 Additive with a(p^e) = A011371(e); the 2-adic valuation of A317934(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 24 2018

nonn

Records are A005187, occurring at A000302 (powers of 4).

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

Cf. A000302, A005187, A011371, A317934.

Cf. also A046645.

f[p_, e_] := e - DigitCount[e, 2, 1]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 21 2024 *)

A011371(n) = (n - hammingweight(n));
A317934(n) = vecsum(apply(e -> A011371(e),factor(n)[,2]));

a(n) = A007814(A317934(n)).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Sum_{p prime, k>=1} 1/(p^(2^k) - 1) = 0.63710219855356676263... . - Amiram Eldar, Jan 21 2024

A181516 Primes in A011371.

Original entry on oeis.org

3, 7, 11, 19, 23, 31, 41, 47, 53, 67, 71, 73, 79, 89, 97, 101, 109, 113, 127, 131, 137, 149, 173, 181, 191, 193, 197, 229, 239, 263, 271, 277, 281, 293, 311, 337, 349, 353, 359, 367, 383, 389, 397, 401, 421, 431, 439, 449, 461, 463, 467, 479, 487, 491, 499

Offset: 1

Vladimir Shevelev, Oct 26 2010

nonn

Primes p such that 2^p divides some factorial m!, but 2^(p+1) does not divide m!.

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

Cf. A011371.

f[n_] := n - DigitCount[n, 2, 1]; s={}; Do[If[PrimeQ[(p = f[n])], AppendTo[s, p]], {n, 1, 510, 2}]; s (* Amiram Eldar, Sep 13 2019 *)
Select[Table[n-DigitCount[n,2,1],{n,0,600}],PrimeQ]//Union (* Harvey P. Dale, Oct 10 2020 *)

Comment and definition swapped by R. J. Mathar, Oct 29 2010

A322983 Number of iterations of A011371(x) = x - A000120(x) needed to reach an odd number, when starting from x = n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 05 2019

Terms 0 .. 10 occur for the first time at n = 1, 2, 6, 12, 126, 192, 486, 492, 498, 504, 65458.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to binary expansion of n

Cf. A000120, A011371, A071542, A179016, A213710, A322984 (bisection).

Cf. also A322996.

A322983(n) = if((n%2),0,1+A322983(n - hammingweight(n)));

If n is odd, a(n) = 0, if n is even, a(n) = 1 + a(A011371(n)).

A322984 Number of iterations of A011371(x) = x - A000120(x) needed to reach an odd number, when starting from x = 2n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 05 2019

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to binary expansion of n

Bisection of A322983.
Cf. A000120, A011371.
Cf. also A322997.

A011371(n) = (n - hammingweight(n));
A322983(n) = if((n%2),0,1+A322983(A011371(n)));
A322984(n) = A322983(n+n);

a(n) = A322983(2*n).

A378992 a(n) = A011371(n) - A048881(n); The exponent of the highest power of 2 dividing the n-th factorial minus the exponent of the highest power of 2 dividing n-th Catalan number.

Original entry on oeis.org

0, 0, 0, 1, 2, 2, 2, 4, 6, 6, 6, 7, 8, 8, 8, 11, 14, 14, 14, 15, 16, 16, 16, 18, 20, 20, 20, 21, 22, 22, 22, 26, 30, 30, 30, 31, 32, 32, 32, 34, 36, 36, 36, 37, 38, 38, 38, 41, 44, 44, 44, 45, 46, 46, 46, 48, 50, 50, 50, 51, 52, 52, 52, 57, 62, 62, 62, 63, 64, 64, 64, 66, 68, 68, 68, 69, 70, 70, 70, 73, 76, 76, 76

Offset: 0

Antti Karttunen, Dec 16 2024

Apparently, after the initial three 0's, only terms of A092054 occur, every other as a single copy, and every other in a batch of 3 duplicated terms.

Antti Karttunen, Table of n, a(n) for n = 0..20000
Index entries for sequences related to binary expansion of n

Partial sums of A050605.
Cf. A000108, A000120, A000142, A007814, A011371, A048881.
Cf. also A092054, A204988, A050603, A136480.

A378992[n_] := n - DigitCount[n, 2, 1] - DigitCount[n + 1, 2, 1] + 1;
Array[A378992, 100, 0] (* or *)
MapIndexed[#2[[1]] - # &, Total[Partition[DigitCount[Range[0, 100], 2, 1], 2, 1], {2}]] (* Paolo Xausa, Dec 28 2024 *)

A378992(n) = (1+(n-hammingweight(n)-hammingweight(1+n)));

a(n) = A007814(A000142(n)) - A007814(A000108(n)) = A011371(n) - A048881(n).

a(0) = 0; for n > 0, a(n) = A050605(n-1) + a(n-1), where A050605(n) = A007814(n+1)+A007814(n+2)-1.

cp's OEIS Frontend

A317934 Multiplicative with a(p^n) = 2^A011371(n); denominators for certain "Dirichlet Square Roots" sequences.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A257264 Square array A(row,col) read by antidiagonals: A(1,col) = A055938(col), and for row > 1, A(row,col) = A011371(A(row-1,col)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

A174605 Partial sums of A011371.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A257507 Row 2 of A257264: a(n) = A011371(A055938(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A297117 Möbius transform of A011371, n minus (number of 1's in binary expansion of n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A317946 Additive with a(p^e) = A011371(e); the 2-adic valuation of A317934(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A181516 Primes in A011371.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A322983 Number of iterations of A011371(x) = x - A000120(x) needed to reach an odd number, when starting from x = n.

Views

Author