A093614 -id:A093614

Search: a093614 -id:a093614

Displaying 1-5 of 5 results found.

page 1

A013939

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

+10
43

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

a(n) = A093614(n) - A048865(n); see also A006218.

A027748(a(A000040(n))+1) = A000040(n), A082287(a(n)+1) = n.

LINKS

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

Eric Weisstein's World of Mathematics, Distinct Prime Factors

FORMULA

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

MAPLE

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

MATHEMATICA

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

PROG

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

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

(PARI) 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

(Haskell)

a013939 n = a013939_list !! (n-1)

a013939_list = scanl1 (+) $ map a001221 [1..]

-- Reinhard Zumkeller, Feb 16 2012

(Python)

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

(Python)

from sympy import primerange

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

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

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

CROSSREFS

Cf. A005187, A006218, A011371, A013936.

Cf. A022559.

Cf. A077761.

Cf. A346617.

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Henri Lifchitz

EXTENSIONS

More terms from Henry Bottomley, Jul 03 2001

STATUS

approved

A048865

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

+10
23

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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.

MAPLE

A048865 := n -> nops(select(isprime, select(k -> igcd(n, k) = 1, [$1..n]))):

seq(A048865(n), n = 1..81); # Peter Luschny, Jul 23 2011

MATHEMATICA

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

PROG

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

(Haskell)

a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]

-- Reinhard Zumkeller, Sep 16 2011

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Labos Elemer

STATUS

approved

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

+10
8

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

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)

FORMULA

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

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

CROSSREFS

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

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, May 14 2006

EXTENSIONS

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

STATUS

approved

A118141

Length of the longest perfect parity pattern with n columns.

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

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.

REFERENCES

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

LINKS

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

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Don Knuth, May 11 2006

EXTENSIONS

More terms from John W. Layman, May 17 2006

More terms from Andries E. Brouwer, Jun 15 2008

STATUS

approved

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.

+10
2

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

REFERENCES

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

LINKS

Table of n, a(n) for n=1..26.

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

CROSSREFS

Cf. A093614 (all elements), A076436.

KEYWORD

nonn,hard,more

AUTHOR

Ralf Stephan, May 22 2004

EXTENSIONS

Gebhardt and Sutner references from Don Knuth, May 11 2006

STATUS

approved

page 1

Search completed in 0.011 seconds