A023506 -id:A023506 - cp's OEIS frontend

A372687 Number of prime numbers whose binary indices sum to n. Number of strict integer partitions y of n such that Sum_i 2^(y_i-1) is prime.

0, 0, 1, 1, 1, 0, 2, 1, 2, 0, 3, 3, 1, 4, 1, 6, 5, 8, 4, 12, 8, 12, 7, 20, 8, 16, 17, 27, 19, 38, 19, 46, 33, 38, 49, 65, 47, 67, 83, 92, 94, 113, 103, 130, 146, 127, 215, 224, 176, 234, 306, 270, 357, 383, 339, 393, 537, 540, 597, 683, 576, 798, 1026, 830, 1157

Offset: 0

Gus Wiseman, May 15 2024

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

Note the inverse of A048793 (binary indices) takes a set s to Sum_i 2^(s_i-1).

			The a(2) = 1 through a(17) = 8 prime numbers:
  2  3  5  .  17  11  19  .  257  131  73  137  97  521  4099  1031
              7       13     67   41       71       263  2053  523
                             37   23       43       139  1033  269
                                           29       83   193   163
                                                    53   47    149
                                                    31         101
                                                               89
                                                               79
The a(2) = 1 through a(11) = 3 strict partitions:
  (2)  (2,1)  (3,1)  .  (5,1)    (4,2,1)  (4,3,1)  .  (9,1)    (6,4,1)
                        (3,2,1)           (5,2,1)     (6,3,1)  (8,2,1)
                                                      (7,2,1)  (5,3,2,1)

For all positive integers (not just prime) we get A000009.
Number of prime numbers p with A029931(p) = n.
For odd instead of prime we have A096765, even A025147, non-strict A087787
Number of times n appears in A372429.
Number of rows of A372471 with sum n.
The non-strict version is A372688 (or A372887), ranks A277319 (or A372850).
These (strict) partitions have Heinz numbers A372851.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
A048793 lists binary indices:
- length A000120
- min A001511
- sum A029931
- max A070939
- reverse A272020
A058698 counts partitions of prime numbers, strict A064688.
A096111 gives product of binary indices.
A372689 lists numbers whose binary indices sum to a prime.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Cf. A000040, A005940, A023506, A029837, A035100, A071814, A230877, A231204, A359359, A372436, A372441.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&PrimeQ[Total[2^#]/2]&]],{n,0,30}]

A372850 Numbers whose distinct prime indices are the binary indices of some prime number.

Original entry on oeis.org

3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 30, 36, 40, 42, 44, 46, 48, 50, 54, 60, 66, 70, 72, 80, 81, 84, 88, 90, 92, 96, 100, 102, 108, 114, 118, 120, 126, 130, 132, 140, 144, 150, 160, 162, 168, 176, 180, 182, 184, 192, 198, 200, 204, 216, 228, 236, 238, 240, 242

Offset: 1

Gus Wiseman, May 16 2024

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
Note the function taking a set s to its rank Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices).

			The distinct prime indices of 45 are {2,3}, which are the binary indices of 6, which is not prime, so 45 is not in the sequence.
The distinct prime indices of 60 are {1,2,3}, which are the binary indices of 7, which is prime, so 60 is in the sequence.
The terms together with their prime indices begin:
    3: {2}
    6: {1,2}
    9: {2,2}
   10: {1,3}
   12: {1,1,2}
   18: {1,2,2}
   20: {1,1,3}
   22: {1,5}
   24: {1,1,1,2}
   27: {2,2,2}
   30: {1,2,3}
   36: {1,1,2,2}
   40: {1,1,1,3}
   42: {1,2,4}
   44: {1,1,5}
   46: {1,9}
   48: {1,1,1,1,2}
   50: {1,3,3}
   54: {1,2,2,2}
   60: {1,1,2,3}
   66: {1,2,5}
   70: {1,3,4}

For even instead of prime we have A005408, with multiplicity A003159.
For odd instead of prime we have  A005843, with multiplicity A036554.
For prime indices with multiplicity we have A277319, counted by A372688.
The squarefree case is A372851, counted by A372687.
Partitions of this type are counted by A372887.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
A048793 and A272020 (reverse) list binary indices:
- length A000120
- min A001511
- sum A029931
- max A070939
A058698 counts partitions of prime numbers, strict A064688.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Cf. A000040, A005940, A023506, A029837, A035100, A071814, A096111, A372429, A372436, A372441, A372471, A372689.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],PrimeQ[Total[2^(Union[prix[#]]-1)]]&]

Numbers k such that Sum_{i:prime(i)|k} 2^(i-1) is prime, where the sum is over the distinct prime indices of k.

A057773 a(n) = Sum_{i=1..n} nu_2(prime(i) - 1) where nu_2(m) = exponent of highest power of 2 dividing m.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 12, 13, 15, 16, 18, 21, 22, 23, 25, 26, 28, 29, 30, 33, 34, 35, 38, 43, 45, 46, 47, 49, 53, 54, 55, 58, 59, 61, 62, 64, 65, 66, 68, 69, 71, 72, 78, 80, 81, 82, 83, 84, 86, 89, 90, 94, 95, 103, 104, 106, 107, 109, 112, 113, 115, 116, 117, 120, 122, 123

Offset: 1

Labos Elemer, Nov 02 2000

nonn

Exponent of highest power of 2 dividing Euler phi of primorials.
Conjecture: a(n) ~ 2n. - Charles R Greathouse IV, Jun 02 2015
The conjecture is true. See the comment in A023506 about the asymptotic distribution of nu_2(prime(i) - 1). - Amiram Eldar, Mar 14 2025

			For n = 6, the 6th primorial is 30030, phi(30030) = 5760 = 2^7 * 3^2 * 5, so a(6) = 7.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A007814, A000010, A002110.

Partial sums of A023506.

a:= proc(n) option remember; `if`(n<2, 0,
      a(n-1)+padic[ordp](ithprime(n)-1, 2))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Jan 01 2023

Table[IntegerExponent[EulerPhi[Product[Prime[i], {i, n}]], 2], {n, 110}] (* Jamie Morken, Oct 13 2023 *)

a(n) = sum(k=1,n, valuation(prime(k)-1, 2)); \\ Michel Marcus, May 30 2015

a(n) = valuation(eulerphi(prod(k=1,n, prime(k))), 2); \\ Michel Marcus, May 30 2015

first(n)=my(p=primes(n),s); vector(#p,i,s+=valuation(p[i]-1,2)) \\ Charles R Greathouse IV, Jun 02 2015

a(n) = A007814(A000010(A002110(n))).

A069177 Maximal power of 2 that divides Phi(n), or the size of the Sylow 2-subgroup of the group of units mod n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 2, 4, 4, 2, 8, 8, 16, 2, 2, 8, 4, 2, 2, 8, 4, 4, 2, 4, 4, 8, 2, 16, 4, 16, 8, 4, 4, 2, 8, 16, 8, 4, 2, 4, 8, 2, 2, 16, 2, 4, 32, 8, 4, 2, 8, 8, 4, 4, 2, 16, 4, 2, 4, 32, 16, 4, 2, 32, 4, 8, 2, 8, 8, 4, 8, 4, 4, 8, 2, 32, 2, 8, 2, 8, 64, 2, 8, 8, 8, 8, 8, 4, 4, 2, 8, 32

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), Apr 09 2002

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

Cf. A000010, A006519, A053574, A023506.

Table[2^IntegerExponent[EulerPhi@ n, 2], {n, 96}] (* Michael De Vlieger, Aug 23 2017 *)

a(n) = 2^valuation(eulerphi(n), 2); \\ Amiram Eldar, Sep 05 2023

(define (A069177 n) (cond ((= 1 n) n) ((zero? (modulo n 4)) (* 2 (A069177 (/ n 2)))) ((even? n) (A069177 (/ n 2))) (else (* (A006519 (+ -1 (A020639 n))) (A069177 (A028234 n)))))) ;; (After Jovovic's multiplicative formula) - Antti Karttunen, Aug 22 2017

a(n) = 2^A053574(n). Multiplicative with a(2^e) = 2^(e-1) and a(p^e) = power of 2 in prime factorization of p - 1 for an odd prime p. - Vladeta Jovovic, Apr 10 2002

More terms from Vladeta Jovovic, Apr 10 2002

A091282 Exponent of 2 in prime(n)^2 - 1.

Original entry on oeis.org

0, 3, 3, 4, 3, 3, 5, 3, 4, 3, 6, 3, 4, 3, 5, 3, 3, 3, 3, 4, 4, 5, 3, 4, 6, 3, 4, 3, 3, 5, 8, 3, 4, 3, 3, 4, 3, 3, 4, 3, 3, 3, 7, 7, 3, 4, 3, 6, 3, 3, 4, 5, 5, 3, 9, 4, 3, 5, 3, 4, 3, 3, 3, 4, 4, 3, 3, 5, 3, 3, 6, 4, 5, 3, 3, 8, 3, 3, 5, 4, 3, 3, 5, 5, 4, 3, 7, 4, 3, 5, 3, 6, 4, 3, 3, 4, 3, 4, 3, 3, 3, 3, 3, 4, 3

Offset: 1

Labos Elemer, Jan 20 2004

nonn

Also, exponent of 2 in -1+prime(n)^s if s is an exponent of the form 4k+2 (previous definition). - Michel Marcus, Dec 20 2013

Primes that give records for this sequence can be found in A233930. - Michel Marcus, Dec 20 2013

			a(1)=0 since -1+2^s is always odd...

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

Cf. A007814, A023506, A023512, A091283, A091284.

IntegerExponent[Prime[Range[100]]^2 - 1, 2] (* Amiram Eldar, Jun 06 2024 *)

a(n) = valuation(prime(n)^2-1, 2); \\ Michel Marcus, Dec 20 2013

a(n) = A023506(n) + A023512(n). - Amiram Eldar, Jun 06 2024

Definition modified by Michel Marcus, Dec 20 2013

A099584 Exponent of 3 in factorization of prime(n) - 1.

Original entry on oeis.org

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

Offset: 1

Ralf Stephan, Oct 24 2004

By Dirichlet's theorem on arithmetic progressions, the asymptotic density of primes p such that p == 1 (mod 3^k) within all the primes is 1/(2*3^(k-1)), for k >= 1. This is also the asymptotic density of terms in this sequence that are >= k. Therefore, the asymptotic density of the occurrences of k in this sequence is d(k) = 1/(2*3^(k-1)) - 1/(2*3^k) = 1/3^k, and the asymptotic mean of this sequence is Sum_{k>=1} k*d(k) = 3/4. - Amiram Eldar, Mar 14 2025

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A006093, A007949, A023506, A099585, A227990.

[Valuation(NthPrime(n)-1, 3): n in [1..110]]; // Bruno Berselli, Aug 05 2013

seq(padic:-ordp(ithprime(i)-1,3), i=1..200); # Robert Israel, Mar 02 2018

Table[IntegerExponent[Prime[n] - 1, 3], {n, 110}] (* Bruno Berselli, Aug 05 2013 *)

forprime(p=2, 700, print1(valuation(p-1,3),", ")); \\ Bruno Berselli, Aug 05 2013

a(n) = A007949(A006093(n)).

prime(n) - 1 = 3^a(n) * A099585(n).

A160216 Primes congruent to 2^k+1 (mod 2^(k+1)), where k is any odd integer >=1.

Original entry on oeis.org

3, 7, 11, 19, 23, 31, 41, 43, 47, 59, 67, 71, 73, 79, 83, 89, 97, 103, 107, 127, 131, 137, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 233, 239, 251, 263, 271, 281, 283, 307, 311, 313, 331, 347, 353, 359, 367, 379, 383, 409, 419, 431, 439, 443, 457, 463

Offset: 1

Vladimir Shevelev, May 04 2009

nonn

Lim_{x -> inf.} the number of terms < x in A160216/A160215 => 2. - Robert G. Wilson v, May 31 2009

Cf. A000040, A160215.

fQ[n_] := Mod[ Flatten[ FactorInteger[n - 1]] [[2]], 2] == 1; Select[ Prime@ Range@ 90, fQ@# &] (* Robert G. Wilson v, May 31 2009 *)

A000040 \ A160215.

{prime(k) : A023506(k) is odd}. - R. J. Mathar, May 08 2009

Edited by R. J. Mathar, May 08 2009

More terms from Robert G. Wilson v, May 31 2009

A160215 Primes congruent to 2^k+1 (mod 2^(k+1)), where k is any even integer >=0.

Original entry on oeis.org

2, 5, 13, 17, 29, 37, 53, 61, 101, 109, 113, 149, 157, 173, 181, 193, 197, 229, 241, 257, 269, 277, 293, 317, 337, 349, 373, 389, 397, 401, 421, 433, 449, 461, 509, 541, 557, 577, 593, 613, 653, 661, 677, 701, 709, 733, 757, 769, 773, 797, 821, 829, 853, 877

Offset: 1

Vladimir Shevelev, May 04 2009

nonn

If A(x) is the counting function of the terms not exceeding x, then A(x) grows similarly to Pi(x)/3, see A000720.

Lim_{x -> inf.} the number of terms < x in A160216/A160215 => 2. - Robert G. Wilson v, May 31 2009

Vincenzo Librandi, Table of n, a(n) for n = 1..2000

Cf. A000040.

fQ[n_] := Mod[ Flatten[ FactorInteger[n - 1]] [[2]], 2] == 0; Select[ Prime@ Range@ 155, fQ@# &] (* Robert G. Wilson v, May 31 2009 *)

A000040 \ A160216.

{prime(k) : A023506(k) is even}. - R. J. Mathar, May 08 2009

Edited by R. J. Mathar, May 08 2009

More terms from Robert G. Wilson v, May 31 2009

A091283 Exponent of 2 in -1+prime[n]^s, if s is an exponent of the form s=8k-4.

Original entry on oeis.org

0, 4, 4, 5, 4, 4, 6, 4, 5, 4, 7, 4, 5, 4, 6, 4, 4, 4, 4, 5, 5, 6, 4, 5, 7, 4, 5, 4, 4, 6, 9, 4, 5, 4, 4, 5, 4, 4, 5, 4, 4, 4, 8, 8, 4, 5, 4, 7, 4, 4, 5, 6, 6, 4, 10, 5, 4, 6, 4, 5, 4, 4, 4, 5, 5, 4, 4, 6, 4, 4, 7, 5, 6, 4, 4, 9, 4, 4, 6, 5, 4, 4, 6, 6, 5, 4, 8, 5, 4, 6, 4, 7, 5, 4, 4, 5, 4, 5, 4, 4, 4, 4, 4, 5, 4

Offset: 1

Labos Elemer, Jan 22 2004

nonn

Cf. A091282, A090739, A090740, A090129, A023506.

Table[{8*k-4, Table[Part[Flatten[FactorInteger [ -1+Prime[n]^(8*k-4)]], 2], {n, 2, m}]}, {k, 1, 2}]

A091284 Exponent of 2 in -1+prime[n]^s, if s is an exponent of form 16k-8. Except a(1)=0, a(n)=1+A091283(n).

Original entry on oeis.org

0, 5, 5, 6, 5, 5, 7, 5, 6, 5, 8, 5, 6, 5, 7, 5, 5, 5, 5, 6, 6, 7, 5, 6, 8, 5, 6, 5, 5, 7, 10, 5, 6, 5, 5, 6, 5, 5, 6, 5, 5, 5, 9, 9, 5, 6, 5, 8, 5, 5

Offset: 1

Labos Elemer, Jan 22 2004

nonn

Exponents of 2 in -1+p^s if the exponent s[u]=(2^u)k-(2^(u-1) comes from other sequence generated with s[u-1] exponent by adding 1 to terms of the "previous" sequence. E.g. s=256k-128 needed an addition of 6 to the terms of A091282.

Cf. A023506, A007814, A091282, A091283, A090739, A090740, A090129.

Table[{8*k-4, Table[Part[Flatten[FactorInteger [ -1+Prime[n]^(16*k-8)]], 2], {n, 2, 50}]}, {k, 1, 2}]

cp's OEIS Frontend

A372687 Number of prime numbers whose binary indices sum to n. Number of strict integer partitions y of n such that Sum_i 2^(y_i-1) is prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A372850 Numbers whose distinct prime indices are the binary indices of some prime number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A057773 a(n) = Sum_{i=1..n} nu_2(prime(i) - 1) where nu_2(m) = exponent of highest power of 2 dividing m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A069177 Maximal power of 2 that divides Phi(n), or the size of the Sylow 2-subgroup of the group of units mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

Extensions

A091282 Exponent of 2 in prime(n)^2 - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A099584 Exponent of 3 in factorization of prime(n) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A160216 Primes congruent to 2^k+1 (mod 2^(k+1)), where k is any odd integer >=1.

Views

Author

Keywords

Comments

Crossrefs

Programs