A093614 -id:A093614 - cp's OEIS frontend

A013939 Partial sums of sequence A001221 (number of distinct primes dividing n).

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, 23, 24, 26, 28, 30, 31, 33, 34, 36, 37, 39, 40, 43, 44, 45, 47, 49, 51, 53, 54, 56, 58, 60, 61, 64, 65, 67, 69, 71, 72, 74, 75, 77, 79, 81, 82, 84, 86, 88, 90, 92, 93, 96, 97, 99, 101, 102, 104, 107, 108, 110, 112

Offset: 1

N. J. A. Sloane, Henri Lifchitz

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Distinct Prime Factors

Cf. A005187, A006218, A011371, A013936.
Cf. A093614, A048865, A006218.
Cf. A027748, A000040, A082287.
Cf. A022559.
Cf. A077761.
Cf. A346617.
Cf. A001222, A048803.

a013939 n = a013939_list !! (n-1)
a013939_list = scanl1 (+) $ map a001221 [1..]
-- Reinhard Zumkeller, Feb 16 2012

[(&+[Floor(n/NthPrime(k)): k in [1..n]]): n in [1..70]]; // G. C. Greubel, Nov 24 2018

A013939 := proc(n) option remember;  `if`(n = 1, 0, a(n) + iquo(n+1, ithprime(n+1))) end:
seq(A013939(i), i = 1..69);  # Peter Luschny, Jul 16 2011

a[n_] := Sum[Floor[n/Prime[k]], {k, 1, n}]; Table[a[n], {n, 1, 69}] (* Jean-François Alcover, Jun 11 2012, from 2nd formula *)
Accumulate[PrimeNu[Range[120]]] (* Harvey P. Dale, Jun 05 2015 *)

t=0;vector(99,n,t+=omega(n)) \\ Charles R Greathouse IV, Jan 11 2012

a(n)=my(s);forprime(p=2,n,s+=n\p);s \\ Charles R Greathouse IV, Jan 11 2012

a(n) = sum(k=1, sqrtint(n), k * (primepi(n\k) - primepi(n\(k+1)))) + sum(k=1, n\(sqrtint(n)+1), if(isprime(k), n\k, 0)); \\ Daniel Suteu, Nov 24 2018

from sympy.ntheory import primefactors
print([sum(len(primefactors(k)) for k in range(1,n+1)) for n in range(1, 121)]) # Indranil Ghosh, Mar 19 2017

from sympy import primerange
def A013939(n): return sum(n//p for p in primerange(n+1)) # Chai Wah Wu, Oct 06 2024

[sum(floor(n/nth_prime(k)) for k in (1..n)) for n in (1..70)] # G. C. Greubel, Nov 24 2018

a(n) = Sum_{k <= n} omega(k).
a(n) = Sum_{k = 1..n} floor( n/prime(k) ).
a(n) = a(n-1) + A001221(n).
a(n) = A093614(n) - A048865(n); see also A006218.
A027748(a(A000040(n))+1) = A000040(n), A082287(a(n)+1) = n.
a(n) = Sum_{k=1..n} pi(floor(n/k)). - Vladeta Jovovic, Jun 18 2006
a(n) = n log log n + O(n). - Charles R Greathouse IV, Jan 11 2012
a(n) = n*(log log n + B) + o(n), where B = 0.261497... is the Mertens constant A077761. - Arkadiusz Wesolowski, Oct 18 2013
G.f.: (1/(1 - x))*Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{k=1..floor(sqrt(n))} k * (pi(floor(n/k)) - pi(floor(n/(k+1)))) + Sum_{p prime <= floor(n/(1+floor(sqrt(n))))} floor(n/p). - Daniel Suteu, Nov 24 2018
a(n) = Sum_{k>=1} k * A346617(n,k). - Alois P. Heinz, Aug 19 2021
a(n) = A001222(A048803(n+1)). - Flávio V. Fernandes, Jan 14 2025

More terms from Henry Bottomley, Jul 03 2001

A048865 a(n) is the number of primes in the reduced residue system mod n.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 3, 3, 2, 4, 3, 5, 4, 4, 5, 6, 5, 7, 6, 6, 6, 8, 7, 8, 7, 8, 7, 9, 7, 10, 10, 9, 9, 9, 9, 11, 10, 10, 10, 12, 10, 13, 12, 12, 12, 14, 13, 14, 13, 13, 13, 15, 14, 14, 14, 14, 14, 16, 14, 17, 16, 16, 17, 16, 15, 18, 17, 17, 16, 19, 18, 20, 19, 19, 19, 19, 18, 21, 20, 21

Offset: 1

Labos Elemer

nonn

The number of primes p <= n with p coprime to n. - Enrique Pérez Herrero, Jul 23 2011

			At n=30 all but 1 element in reduced residue system of 30 are primes (see A048597) so a(30) = Phi(30) - 1 = 7.
n=100: a(100) = Pi(100) - A001221(100) = 25 - 2 = 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000010, A000720, A001221, A010051, A048597, A070296, A368616, A368641.

a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]
-- Reinhard Zumkeller, Sep 16 2011

A048865 := n ->  nops(select(isprime, select(k -> igcd(n,k) = 1, [$1..n]))):
seq(A048865(n), n = 1..81); # Peter Luschny, Jul 23 2011

p=Prime[Range[1000]]; q=Table[PrimePi[i], {i, 1, 1000}]; t=Table[c=0; Do[If[GCD[p[[j]], i]==1, c++ ], {j, 1, q[[i-1]]}]; c, {i, 2, 950}]
Table[Count[Select[Range@ n, CoprimeQ[#, n] &], p_ /; PrimeQ@ p], {n, 81}] (* Michael De Vlieger, Apr 27 2016 *)
Table[PrimePi[n] - PrimeNu[n], {n, 50}] (* G. C. Greubel, May 16 2017 *)

PARI
```
A048865(n)=primepi(n)-omega(n)
```

a(n) = A000720(n) - A001221(n).
From Reinhard Zumkeller, Apr 05 2004: (Start)
a(n) = Sum_{p prime and p<=n} (ceiling(n/p) - floor(n/p)).
a(n) = A093614(n) - A013939(n). (End)
a(n) = A001221(A001783(n)). - Enrique Pérez Herrero, Jul 23 2011
a(n) = A368616(n) - A368641(n). - Wesley Ivan Hurt, Jan 01 2024

A117870 Square board sizes for which the lights out problem does not have a unique solution (counting solutions differing only by rotation and reflection as distinct).

Original entry on oeis.org

4, 5, 9, 11, 14, 16, 17, 19, 23, 24, 29, 30, 32, 33, 34, 35, 39, 41, 44, 47, 49, 50, 53, 54, 59, 61, 62, 64, 65, 67, 69, 71, 74, 77, 79, 83, 84, 89, 92, 94, 95, 98, 99, 101, 104, 107, 109, 113, 114, 118, 119, 123, 124, 125, 126, 128, 129, 131, 134, 135, 137, 139, 143

Offset: 1

N. J. A. Sloane, May 14 2006

nonn

Numbers k such that a k X k parity pattern exists (see A118141). - Don Knuth, May 11 2006

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by Max Alekseyev, Sep 17 2009; terms 64 through 1000 were computed by Thomas Buchholz, May 16 2014]
Jaap's puzzle page, The Mathematics of Lights Out
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle
Wikipedia, Lights Out (game)

Cf. A075462, A076437, A117872. Complement of A076436.

a(n) = A093614(n) - 1.

Contains positive integers k such that A159257(k) > 0. - Max Alekseyev, Sep 17 2009

More terms from Max Alekseyev, Sep 17 2009, and Thomas Buchholz, May 16 2014

A118141 Length of the longest perfect parity pattern with n columns.

Original entry on oeis.org

2, 3, 5, 4, 23, 8, 11, 27, 29, 30, 47, 62, 17, 339, 23, 254, 167, 512, 59, 2339, 185, 2046, 95, 1024, 125, 2043, 35, 3276, 2039, 340, 47, 4091, 509, 4094, 335, 3590, 1025, 16379, 119, 1048574, 4679, 16382, 371, 92819, 12281, 8388606, 191, 2097152, 6149, 262139

Offset: 1

Don Knuth, May 11 2006

nonn

Also the length of the unique perfect parity pattern whose first row is 0....01 (with n-1 zeros).
Definitions: A parity pattern is a matrix of 0's and 1's with the property that every 0 is adjacent to an even number of 1's and every 1 is adjacent to an odd number of 1's.
It is called perfect if no row or column is entirely zero. Every parity pattern can be built up in a straightforward way from the smallest perfect subpattern in its upper left corner.
For example, the 3 X 2 matrix
11
00
11
is a parity pattern built up from the perfect 1 X 2 pattern "11". The 3 X 5 matrix
01010
11011
01010
is similarly built up from the perfect 3 X 2 pattern of its first two columns. The 4 X 4 matrix
0011
0100
1101
0101
is perfect. So is the 5 X 5
01110
10101
11011
10101
01110
which moreover has 8-fold symmetry (cf. A118143).
All perfect parity patterns of n columns can be shown to have length d-1 where d divides a(n)+1.

D. E. Knuth, The Art of Computer Programming, Section 7.1.3.

Andries E. Brouwer, Jun 15 2008, Table of n, a(n) for n = 1..85
Andries E. Brouwer, Button Madness and Lights Out on rectangles

The number of perfect parity patterns that have exactly n columns is A000740.
The sequence of all n such that an n X n parity pattern exists is A117870 (cf. A076436, A093614, A094425).
Cf. also A118142, A118143.
Cf. A007802.

More terms from John W. Layman, May 17 2006

More terms from Andries E. Brouwer, Jun 15 2008

A094425 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind; this lists only the primitive elements of the set.

Original entry on oeis.org

5, 6, 17, 31, 33, 63, 127, 129, 171, 257, 511, 683, 2047, 2731, 2979, 3277, 3641, 8191, 28197, 43691, 48771, 52429, 61681, 65537, 85489, 131071

Offset: 1

Ralf Stephan, May 22 2004

Klaus Sutner, Jun 26 2006, remarks that it can be shown that this sequence is infinite.

Dieter Gebhardt, "Cross pattern puzzles revisited," Cubism For Fun 69 (March 2006), 23-25.

K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
K. Sutner, The computational complexity of cellular automata, in Lect. Notes Computer Sci., 380 (1989), 451-459.
K. Sutner, sigma-Automata and Chebyshev-polynomials, Theoretical Comp. Sci., 230 (2000), 49-73.
M. Hunziker, A. Machiavelo and J. Park, Chebyshev polynomials over finite fields and reversibility of sigma-automata on square grids, Theoretical Comp. Sci., 320 (2004), 465-483.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle

Cf. A093614 (all elements), A076436.

Gebhardt and Sutner references from Don Knuth, May 11 2006

cp's OEIS Frontend

A013939 Partial sums of sequence A001221 (number of distinct primes dividing n).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Sage

Formula

Extensions

A048865 a(n) is the number of primes in the reduced residue system mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A117870 Square board sizes for which the lights out problem does not have a unique solution (counting solutions differing only by rotation and reflection as distinct).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A118141 Length of the longest perfect parity pattern with n columns.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A094425 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind; this lists only the primitive elements of the set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions