Search: kimberley
|
| |
|
|
A001222
|
|
Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)).
(Formerly M0094 N0031)
|
|
+10
2899
|
|
|
|
0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Maximal number of terms in any factorization of n.
Number of prime powers (not including 1) that divide n.
Sum of exponents in prime-power factorization of n. - Daniel Forgues, Mar 29 2009
Sum_{d|n} 2^(-A001221(d) - a(n/d)) = Sum_{d|n} 2^(-a(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012
Conjecture: Let f(n) = (x+y)^a(n), and g(n) = x^a(n), and h(n) = (x+y)^A046660(n) * y^A001221(n) with x, y complex numbers and 0^0 = 1. Then f(n) = Sum_{d|n} g(d)*h(n/d). This is proved for x = 1-y (see Dressler and van de Lune link). - Werner Schulte, Feb 10 2018
Let r, s be some fixed integers. Then we have:
(1) The sequence b(n) = Dirichlet convolution of r^bigomega(n) and s^bigomega(n) is multiplicative with b(p^e) = (r^(e+1)-s^(e+1))/(r-s) for prime p and e >= 0. The case r = s leads to b(p^e) = (e+1)*r^e.
(2) The sequence c(n) = Dirichlet convolution of r^bigomega(n) and mu(n)*s^bigomega(n) is multiplicative with c(p^e) = (r-s)*r^(e-1) and c(1) = 1 for prime p and e > 0 where mu(n) = A008683(n). - Werner Schulte, Feb 20 2019
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 119, #12, omega(n).
M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.
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).
|
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 844.
Eric Weisstein's World of Mathematics, Roundness
|
|
|
FORMULA
|
n = Product_(p_j^k_j) -> a(n) = Sum_(k_j).
Dirichlet g.f.: ppzeta(s)*zeta(s). Here ppzeta(s) = Sum_{p prime} Sum_{k>=1} 1/(p^k)^s. Note that ppzeta(s) = Sum_{p prime} 1/(p^s-1) and ppzeta(s) = Sum_{k>=1} primezeta(k*s). - Franklin T. Adams-Watters, Sep 11 2005
Totally additive with a(p) = 1.
G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 2017
|
|
|
EXAMPLE
|
16=2^4, so a(16)=4; 18=2*3^2, so a(18)=3.
|
|
|
MAPLE
|
with(numtheory): seq(bigomega(n), n=1..111);
|
|
|
MATHEMATICA
|
Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105]
|
|
|
PROG
|
(PARI) vector(100, n, bigomega(n))
(Magma) [n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // Bruno Berselli, Nov 27 2013
(Haskell)
import Math.NumberTheory.Primes.Factorisation (factorise)
a001222 = sum . snd . unzip . factorise
(Scheme)
(define (A001222 n) (let loop ((n n) (z 0)) (if (= 1 n) z (loop (/ n (A020639 n)) (+ 1 z)))))
;; Requires also A020639 for which an equally naive implementation can be found under that entry. - Antti Karttunen, Apr 12 2017
(GAP) Concatenation([0], List([2..150], n->Length(Factors(n)))); # Muniru A Asiru, Feb 21 2019
(Python)
from sympy import primeomega
def a(n): return primeomega(n)
(Julia)
using Nemo
function NumberOfPrimeFactors(n; distinct=true)
distinct && return length(factor(ZZ(n)))
sum(e for (p, e) in factor(ZZ(n)); init=0)
end
println([NumberOfPrimeFactors(n, distinct=false) for n in 1:60]) # Peter Luschny, Jan 02 2024
|
|
|
CROSSREFS
|
Sequences listing n such that a(n) = r: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20). - _Jason Kimberley_, Oct 02 2011
Cf. A079149 (primes adj. to integers with at most 2 prime factors, a(n)<=2).
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000012
|
|
The simplest sequence of positive numbers: the all 1's sequence.
(Formerly M0003)
|
|
+10
2445
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
(list;
table;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
Number of ways of writing n as a product of primes.
Number of ways of writing n as a sum of distinct powers of 2.
Continued fraction for golden ratio A001622.
An example of an infinite sequence of positive integers whose distinct pairwise concatenations are all primes! - Don Reble, Apr 17 2005
For n >= 0, let M(n) be the matrix with first row = (n n+1) and 2nd row = (n+1 n+2). Then a(n) = absolute value of det(M(n)). - K.V.Iyer, Apr 11 2009
a(n) is also tau_1(n) where tau_2(n) is A000005.
a(n) is a completely multiplicative arithmetical function.
a(n) is both squarefree and a perfect square. See A005117 and A000290. (End)
a(n) is also the number of complete graphs on n nodes. - Pablo Chavez (pchavez(AT)cmu.edu), Sep 15 2009
Totally multiplicative sequence with a(p) = 1 for prime p. Totally multiplicative sequence with a(p) = a(p-1) for prime p. - Jaroslav Krizek, Oct 18 2009
n-th prime minus phi(prime(n)); number of divisors of n-th prime minus number of perfect partitions of n-th prime; the number of perfect partitions of n-th prime number; the number of perfect partitions of n-th noncomposite number. - Juri-Stepan Gerasimov, Oct 26 2009
For all n>0, the sequence of limit values for a(n) = n!*Sum_{k>=n} k/(k+1)!. Also, a(n) = n^0. - Harlan J. Brothers, Nov 01 2009
a(n) is also the number of 0-regular graphs on n vertices. - _Jason Kimberley_, Nov 07 2009
1) When sequence is read as a regular triangular array, T(n,k) is the coefficient of the k-th power in the expansion of (x^(n+1)-1)/(x-1).
2) Sequence can also be read as a uninomial array with rows of length 1, analogous to arrays of binomial, trinomial, etc., coefficients. In a q-nomial array, T(n,k) is the coefficient of the k-th power in the expansion of ((x^q -1)/(x-1))^n, and row n has a sum of q^n and a length of (q-1)*n + 1. (End)
The number of maximal self-avoiding walks from the NW to SW corners of a 2 X n grid.
a(n) = A007310(n+1) (Modd 3) := A193680(A007310(n+1)), n>=0. For general Modd n (not to be confused with mod n) see a comment on A203571. The nonnegative members of the three residue classes Modd 3, called [0], [1], and [2], are shown in the array A088520, if there the third row is taken as class [0] after inclusion of 0. - Wolfdieter Lang, Feb 09 2012
Let M = Pascal's triangle without 1's (A014410) and V = a variant of the Bernoulli numbers A027641 but starting [1/2, 1/6, 0, -1/30, ...]. Then M*V = [1, 1, 1, 1, ...]. - Gary W. Adamson, Mar 05 2012
As a lower triangular array, T is an example of the fundamental generalized factorial matrices of A133314. Multiplying each n-th diagonal by t^n gives M(t) = I/(I-t*S) = I + t*S + (t*S)^2 + ... where S is the shift operator A129184, and T = M(1). The inverse of M(t) is obtained by multiplying the first subdiagonal of T by -t and the other subdiagonals by zero, so A167374 is the inverse of T. Multiplying by t^n/n! gives exp(t*S) with inverse exp(-t*S). - Tom Copeland, Nov 10 2012
The original definition of the meter was one ten-millionth of the distance from the Earth's equator to the North Pole. According to that historical definition, the length of one degree of latitude, that is, 60 nautical miles, would be exactly 111111.111... meters. - Jean-François Alcover, Jun 02 2013
Consider n >= 1 nonintersecting spheres each with surface area S. Define point p on sphere S_i to be a "public point" if and only if there exists a point q on sphere S_j, j != i, such that line segment pq INTERSECT S_i = {p} and pq INTERSECT S_j = {q}; otherwise, p is a "private point". The total surface area composed of exactly all private points on all n spheres is a(n)*S = S. ("The Private Planets Problem" in Zeitz.) - Rick L. Shepherd, May 29 2014
A fixed point of the run length transform. - Chai Wah Wu, Oct 21 2016
a(n) is also the determinant of the (n+1) X (n+1) matrix M defined by M(i,j) = binomial(i,j) for 0 <= i,j <= n, since M is a lower triangular matrix with main diagonal all 1's. - Jianing Song, Jul 17 2018
a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j) for 1 <= i,j <= n (see Xavier Merlin reference). - Bernard Schott, Dec 05 2018
a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = tau(gcd(i,j)) for 1 <= i,j <= n (see De Koninck & Mercier reference). - Bernard Schott, Dec 08 2020
|
|
|
REFERENCES
|
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 692 pp. 90 and 297, Ellipses, Paris, 2004.
Xavier Merlin, Méthodix Algèbre, Exercice 1-a), page 153, Ellipses, Paris, 1995.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
Paul Zeitz, The Art and Craft of Mathematical Problem Solving, The Great Courses, The Teaching Company, 2010 (DVDs and Course Guidebook, Lecture 6: "Pictures, Recasting, and Points of View", pp. 32-34).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 1.
G.f.: 1/(1-x).
E.g.f.: exp(x).
G.f.: Product_{k>=0} (1 + x^(2^k)). - Zak Seidov, Apr 06 2007
Completely multiplicative with a(p^e) = 1.
Regarded as a square array by antidiagonals, g.f. 1/((1-x)(1-y)), e.g.f. Sum T(n,m) x^n/n! y^m/m! = e^{x+y}, e.g.f. Sum T(n,m) x^n y^m/m! = e^y/(1-x). Regarded as a triangular array, g.f. 1/((1-x)(1-xy)), e.g.f. Sum T(n,m) x^n y^m/m! = e^{xy}/(1-x). - Franklin T. Adams-Watters, Feb 06 2006
a(n) = Sum_{l=1..n} (-1)^(l+1)*2*cos(Pi*l/(2*n+1)) = 1 identically in n >= 1 (for n=0 one has 0 from the undefined sum). From the Jolley reference, (429) p. 80. Interpretation: consider the n segments between x=0 and the n positive zeros of the Chebyshev polynomials S(2*n, x) (see A049310). Then the sum of the lengths of every other segment starting with the one ending in the largest zero (going from the right to the left) is 1. - Wolfdieter Lang, Sep 01 2016
|
|
|
EXAMPLE
|
1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + ...)))) = A001622.
1/9 = 0.11111111111111...
Modd 7 for nonnegative odd numbers not divisible by 3:
A007310: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
Modd 3: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
(End)
|
|
|
MAPLE
|
seq(1, i=0..150);
|
|
|
MATHEMATICA
|
Array[1 &, 50] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
|
|
|
PROG
|
(Magma) [1 : n in [0..100]];
(PARI) {a(n) = 1};
(Haskell)
a000012 = const 1
(Maxima) makelist(1, n, 1, 30); /* Martin Ettl, Nov 07 2012 */
|
|
|
CROSSREFS
|
Cf. A000004, A007395, A010701, A000027, A027641, A014410, A211216, A212393, A060544, A051801, A104684.
|
|
|
KEYWORD
|
nonn,core,easy,mult,cofr,cons,tabl,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A001358
|
|
Semiprimes (or biprimes): products of two primes.
(Formerly M3274 N1323)
|
|
+10
1716
|
|
|
|
4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Numbers of the form p*q where p and q are primes, not necessarily distinct.
These numbers are sometimes called semi-primes or 2-almost primes. In this database the official spelling is "semiprime", not "semi-prime".
Numbers n such that Omega(n) = 2 where Omega(n) = A001222(n) is the sum of the exponents in the prime decomposition of n.
The graph of this sequence appears to be a straight line with slope 4. However, the asymptotic formula shows that the linearity is an illusion and in fact a(n)/n ~ log(n)/log(log(n)) goes to infinity. See also the graph of A066265 = number of semiprimes < 10^n.
For numbers between 33 and 15495, semiprimes are more plentiful than any other k-almost prime. See A125149.
Numbers that are divisible by exactly 2 prime powers (not including 1). - _Jason Kimberley_, Oct 02 2011
The (disjoint) union of A006881 and A001248. - _Jason Kimberley_, Nov 11 2015
An equivalent definition of this sequence is a'(n) = smallest composite number which is not divided by any smaller composite number a'(1),...,a'(n-1). - Meir-Simchah Panzer, Jun 22 2016
The above characterization can be simplified to "Composite numbers not divisible by a smaller term." This shows that this is the equivalent of primes computed via Eratosthenes's sieve, but starting with the set of composite numbers (i.e., complement of 1 union primes) instead of all positive integers > 1. It's easy to see that iterating the method (using Eratosthenes's sieve each time on the remaining numbers, complement of the previously computed set) yields numbers with bigomega = k for k = 0, 1, 2, 3, ..., i.e., {1}, A000040, this, A014612, etc. - M. F. Hasler, Apr 24 2019
|
|
|
REFERENCES
|
Archimedeans Problems Drive, Eureka, 17 (1954), 8.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; Chapter II, Problem 60.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Vol. 1, Teubner, Leipzig; third edition: Chelsea, New York (1974). See p. 211.
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).
|
|
|
LINKS
|
Daniel A. Goldston, Sidney W. Graham, János Pintz and Cem Y. Yildirim, Small gaps between primes or almost primes, Transactions of the American Mathematical Society, Vol. 361, No. 10 (2009), pp. 5285-5330, arXiv preprint, arXiv:math/0506067 [math.NT], 2005.
Sh. T. Ishmukhametov and F. F. Sharifullina, On distribution of semiprime numbers, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2014, No. 8, pp. 53-59. English translation, Russian Mathematics, Vol. 58, No. 8 (2014), pp. 43-48, alternative link.
Dixon Jones, Quickie 593, Mathematics Magazine, Vol. 47, No. 3, May 1974, p. 167.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909. See Vol. 1, p. 211.
Eric Weisstein's World of Mathematics, Semiprime.
|
|
|
FORMULA
|
a(n) ~ n*log(n)/log(log(n)) as n -> infinity [Landau, p. 211], [Ayoub].
Recurrence: a(1) = 4; for n > 1, a(n) = smallest composite number which is not a multiple of any of the previous terms. - Amarnath Murthy, Nov 10 2002
Sum_{n>=1} 1/a(n)^s = (1/2)*(P(s)^2 + P(2*s)), where P is the prime zeta function. - Enrique Pérez Herrero, Jun 24 2012
sigma(a(n)) + phi(a(n)) - mu(a(n)) = 2*a(n) + 1. mu(a(n)) = ceiling(sqrt(a(n))) - floor(sqrt(a(n))). - Wesley Ivan Hurt, May 21 2013
mu(a(n)) = -Omega(a(n)) + omega(a(n)) + 1, where mu is the Moebius function (A008683), Omega is the count of prime factors with repetition, and omega is the count of distinct prime factors. - Alonso del Arte, May 09 2014
|
|
|
EXAMPLE
|
The sequence of terms together with their prime factors begins:
4 = 2*2 46 = 2*23 91 = 7*13 141 = 3*47
6 = 2*3 49 = 7*7 93 = 3*31 142 = 2*71
9 = 3*3 51 = 3*17 94 = 2*47 143 = 11*13
10 = 2*5 55 = 5*11 95 = 5*19 145 = 5*29
14 = 2*7 57 = 3*19 106 = 2*53 146 = 2*73
15 = 3*5 58 = 2*29 111 = 3*37 155 = 5*31
21 = 3*7 62 = 2*31 115 = 5*23 158 = 2*79
22 = 2*11 65 = 5*13 118 = 2*59 159 = 3*53
25 = 5*5 69 = 3*23 119 = 7*17 161 = 7*23
26 = 2*13 74 = 2*37 121 = 11*11 166 = 2*83
33 = 3*11 77 = 7*11 122 = 2*61 169 = 13*13
34 = 2*17 82 = 2*41 123 = 3*41 177 = 3*59
35 = 5*7 85 = 5*17 129 = 3*43 178 = 2*89
38 = 2*19 86 = 2*43 133 = 7*19 183 = 3*61
39 = 3*13 87 = 3*29 134 = 2*67 185 = 5*37
(End)
|
|
|
MAPLE
|
A001358 := proc(n) option remember; local a; if n = 1 then 4; else for a from procname(n-1)+1 do if numtheory[bigomega](a) = 2 then return a; end if; end do: end if; end proc:
|
|
|
MATHEMATICA
|
Select[Range[200], Plus@@Last/@FactorInteger[#] == 2 &] (* Zak Seidov, Jun 14 2005 *)
Select[Range[200], PrimeOmega[#]==2&] (* Harvey P. Dale, Jul 17 2011 *)
|
|
|
PROG
|
(PARI) select( isA001358(n)={bigomega(n)==2}, [1..199]) \\ M. F. Hasler, Apr 09 2008; added select() Apr 24 2019
(PARI) list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, listput(v, t*q))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Sep 11 2011
(PARI) A1358=List(4); A001358(n)={while(#A1358<n, my(t=A1358[#A1358]); until(bigomega(t++)==2, ); listput(A1358, t)); A1358[n]} \\ M. F. Hasler, Apr 24 2019
(Haskell)
a001358 n = a001358_list !! (n-1)
a001358_list = filter ((== 2) . a001222) [1..]
(Magma) [n: n in [2..200] | &+[d[2]: d in Factorization(n)] eq 2]; // Bruno Berselli, Sep 09 2015
(Python)
from sympy import factorint
def ok(n): return sum(factorint(n).values()) == 2
|
|
|
CROSSREFS
|
Cf. A064911 (characteristic function).
Cf. A077554, A077555, A002024, A072966, A100592, A014673, A068318, A061299, A087718, A089994, A089995, A096916, A096932, A106550, A106554, A108541, A108542, A126663, A131284, A138510, A138511, A072931, A088183, A171963, A237040 (semiprimes of form n^3 + 1).
Sequences listing r-almost primes, that is, the n such that A001222(n) = r: A000040 (r=1), this sequence (r=2), A014612 (r=3), A014613 (r=4), A014614 (r=5), A046306 (r=6), A046308 (r=7), A046310 (r=8), A046312 (r=9), A046314 (r=10), A069272 (r=11), A069273 (r=12), A069274 (r=13), A069275 (r=14), A069276 (r=15), A069277 (r=16), A069278 (r=17), A069279 (r=18), A069280 (r=19), A069281 (r=20).
These are the Heinz numbers of length-2 partitions, counted by A004526.
Grouping by greater factor gives A087112.
The terms with relatively prime/divisible prime indices are A300912/A318990.
Factorizations using these terms are counted by A320655.
Grouping by weight (sum of prime indices) gives A338904, with row sums A024697.
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A005117
|
|
Squarefree numbers: numbers that are not divisible by a square greater than 1.
(Formerly M0617)
|
|
+10
1609
|
|
|
|
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
1 together with the numbers that are products of distinct primes.
Also smallest sequence with the property that a(m)*a(k) is never a square for k != m. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001
Numbers k such that there is only one Abelian group with k elements, the cyclic group of order k (the numbers such that A000688(k) = 1). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 25 2001
a(n) is the smallest m with exactly n squarefree numbers <= m. - Amarnath Murthy, May 21 2002
k is squarefree <=> k divides prime(k)# where prime(k)# = product of first k prime numbers. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 30 2004
The LCM of any finite subset is in this sequence. - Lekraj Beedassy, Jul 11 2006
This sequence and the Beatty Pi^2/6 sequence (A059535) are "incestuous": the first 20000 terms are bounded within (-9, 14). - Ed Pegg Jr, Jul 22 2008
Let us introduce a function D(n) = sigma_0(n)/2^(alpha(1) + ... + alpha(r)), sigma_0(n) number of divisors of n (A000005), prime factorization of n = p(1)^alpha(1) * ... * p(r)^alpha(r), alpha(1) + ... + alpha(r) is sequence (A086436). Function D(n) splits the set of positive integers into subsets, according to the value of D(n). Squarefree numbers (A005117) has D(n)=1, other numbers are "deviated" from the squarefree ideal and have 0 < D(n) < 1. For D(n)=1/2 we have A048109, for D(n)=3/4 we have A067295. - Ctibor O. Zizka, Sep 21 2008
Numbers k such that sqrt(k) cannot be simplified. - Sean Loughran, Sep 04 2011
Indices m where A057918(m)=0, i.e., positive integers m for which there are no integers k in {1,2,...,m-1} such that k*m is a square. - John W. Layman, Sep 08 2011
It appears that these are numbers j such that Product_{k=1..j} (prime(k) mod j) = 0 (see Maple code). - Gary Detlefs, Dec 07 2011. - This is the same claim as Mohammed Bouayoun's Mar 30 2004 comment above. To see why it holds: Primorial numbers, A002110, a subsequence of this sequence, are never divisible by any nonsquarefree number, A013929, and on the other hand, the index of the greatest prime dividing any n is less than n. Cf. A243291. - Antti Karttunen, Jun 03 2014
Conjecture: For each n=2,3,... there are infinitely many integers b > a(n) such that Sum_{k=1..n} a(k)*b^(k-1) is prime, and the smallest such an integer b does not exceed (n+3)*(n+4). - Zhi-Wei Sun, Mar 26 2013
The probability that a random natural number belongs to the sequence is 6/Pi^2, A059956 (see Cesàro reference). - Giorgio Balzarotti, Nov 21 2013
Booker, Hiary, & Keating give a subexponential algorithm for testing membership in this sequence without factoring. - Charles R Greathouse IV, Jan 29 2014
Because in the factorizations into prime numbers these a(n) (n >= 2) have exponents which are either 0 or 1 one could call the a(n) 'numbers with a fermionic prime number decomposition'. The levels are the prime numbers prime(j), j >= 1, and the occupation numbers (exponents) e(j) are 0 or 1 (like in Pauli's exclusion principle). A 'fermionic state' is then denoted by a sequence with entries 0 or 1, where, except for the zero sequence, trailing zeros are omitted. The zero sequence stands for a(1) = 1. For example a(5) = 6 = 2^1*3^1 is denoted by the 'fermionic state' [1, 1], a(7) = 10 by [1, 0, 1]. Compare with 'fermionic partitions' counted in A000009. - Wolfdieter Lang, May 14 2014
The following is an Eratosthenes-type sieve for squarefree numbers. For integers > 1:
1) Remove even numbers, except for 2; the minimal non-removed number is 3.
2) Replace multiples of 3 removed in step 1, and remove multiples of 3 except for 3 itself; the minimal non-removed number is 5.
3) Replace multiples of 5 removed as a result of steps 1 and 2, and remove multiples of 5 except for 5 itself; the minimal non-removed number is 6.
4) Replace multiples of 6 removed as a result of steps 1, 2 and 3 and remove multiples of 6 except for 6 itself; the minimal non-removed number is 7.
5) Repeat using the last minimal non-removed number to sieve from the recovered multiples of previous steps.
Proof. We use induction. Suppose that as a result of the algorithm, we have found all squarefree numbers less than n and no other numbers. If n is squarefree, then the number of its proper divisors d > 1 is even (it is 2^k - 2, where k is the number of its prime divisors), and, by the algorithm, it remains in the sequence. Otherwise, n is removed, since the number of its squarefree divisors > 1 is odd (it is 2^k-1).
(End)
The lexicographically least sequence of integers > 1 such that each entry has an even number of proper divisors occurring in the sequence (that's the sieve restated). - Glen Whitney, Aug 30 2015
0 is nonsquarefree because it is divisible by any square. - Jon Perry, Nov 22 2014, edited by M. F. Hasler, Aug 13 2015
The Heinz numbers of partitions with distinct parts. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} prime(j) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] the Heinz number is 2*2*3*7*29 = 2436. The number 30 (= 2*3*5) is in the sequence because it is the Heinz number of the partition [1,2,3]. - Emeric Deutsch, May 21 2015
It is possible for 2 consecutive terms to be even; for example a(258)=422 and a(259)=426. - Thomas Ordowski, Jul 21 2015. [These form a subsequence of A077395 since their product is divisible by 4. - M. F. Hasler, Aug 13 2015]
There are never more than 3 consecutive terms. Runs of 3 terms start at 1, 5, 13, 21, 29, 33, ... (A007675). - Ivan Neretin, Nov 07 2015
Numbers k such that b^(phi(k)+1) == b (mod k) for every integer b. - Thomas Ordowski, Oct 09 2016
Boreico shows that the set of square roots of the terms of this sequence is linearly independent over the rationals. - _Jason Kimberley_, Nov 25 2016 (reference found by Michael Coons).
The prime zeta function P(s) "has singular points along the real axis for s=1/k where k runs through all positive integers without a square factor". See Wolfram link. - Maleval Francis, Jun 23 2018
The Schnirelmann density of the squarefree numbers is 53/88 (Rogers, 1964). - Amiram Eldar, Mar 12 2021
Numbers k such that all groups of order k have a trivial Frattini subgroup [Dummit and Foote].
Let the group G have order n. If n is squarefree and n > 1, then G is solvable, and thus by Hall's Theorem contains a subgroup H_p of index p for all p | n. Each H_p is maximal in G by order considerations, and the intersection of all the H_p's is trivial. Thus G's Frattini subgroup Phi(G), being the intersection of G's maximal subgroups, must be trivial. If n is not squarefree, the cyclic group of order n has a nontrivial Frattini subgroup. (End)
Numbers for which the squarefree divisors (A206778) and the unitary divisors (A077610) are the same; moreover they are also the set of divisors (A027750). - Bernard Schott, Nov 04 2022
|
|
|
REFERENCES
|
Jean-Marie De Koninck, Ces nombres qui nous fascinent, Entry 165, p. 53, Ellipses, Paris, 2008.
Dummit, David S., and Richard M. Foote. Abstract algebra. Vol. 1999. Englewood Cliffs, NJ: Prentice Hall, 1991.
Ivan M. Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 251.
Michael Pohst and Hans J. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, page 432.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Srinivasa Ramanujan, Irregular numbers, J. Indian Math. Soc., Vol. 5 (1913), pp. 105-106.
Eric Weisstein's World of Mathematics, Squarefree.
|
|
|
FORMULA
|
|a(n) - n*Pi^2/6| < 0.058377*sqrt(n) for n >= 268293; this result can be derived from Cohen, Dress, & El Marraki, see links. - Charles R Greathouse IV, Jan 18 2018
Sum_{n>=1} (-1)^(a(n)+1)/a(n)^2 = 9/Pi^2.
Sum_{k=1..n} 1/a(k) ~ (6/Pi^2) * log(n).
Sum_{k=1..n} (-1)^(a(k)+1)/a(k) ~ (2/Pi^2) * log(n).
(all from Scott, 2006) (End)
|
|
|
MAPLE
|
with(numtheory); a := [ ]; for n from 1 to 200 do if issqrfree(n) then a := [ op(a), n ]; fi; od:
t:= n-> product(ithprime(k), k=1..n): for n from 1 to 113 do if(t(n) mod n = 0) then print(n) fi od; # Gary Detlefs, Dec 07 2011
A005117 := proc(n) option remember; if n = 1 then 1; else for a from procname(n-1)+1 do if numtheory[issqrfree](a) then return a; end if; end do: end if; end proc: # R. J. Mathar, Jan 09 2013
|
|
|
MATHEMATICA
|
Select[Range[150], Max[Last /@ FactorInteger[ # ]] < 2 &] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NextSquareFree[n_, k_: 1] := Block[{c = 0, sgn = Sign[k]}, sf = n + sgn; While[c < Abs[k], While[ ! SquareFreeQ@ sf, If[sgn < 0, sf--, sf++]]; If[ sgn < 0, sf--, sf++]; c++]; sf + If[ sgn < 0, 1, -1]]; NestList[ NextSquareFree, 1, 70] (* Robert G. Wilson v, Apr 18 2014 *)
|
|
|
PROG
|
(Magma) [ n : n in [1..1000] | IsSquarefree(n) ];
(PARI) bnd = 1000; L = vector(bnd); j = 1; for (i=1, bnd, if(issquarefree(i), L[j]=i; j=j+1)); L
(PARI) {a(n)= local(m, c); if(n<=1, n==1, c=1; m=1; while( c<n, m++; if(issquarefree(m), c++)); m)} /* Michael Somos, Apr 29 2005 */
(PARI) list(n)=my(v=vectorsmall(n, i, 1), u, j); forprime(p=2, sqrtint(n), forstep(i=p^2, n, p^2, v[i]=0)); u=vector(sum(i=1, n, v[i])); for(i=1, n, if(v[i], u[j++]=i)); u \\ Charles R Greathouse IV, Jun 08 2012
(PARI)
S(n) = my(s); forsquarefree(k=1, sqrtint(n), s+=n\k[1]^2*moebius(k)); s;
a(n) = my(min=1, max=231, k=0, sc=0); if(n >= 144, min=floor(zeta(2)*n - 5*sqrt(n)); max=ceil(zeta(2)*n + 5*sqrt(n))); while(min <= max, k=(min+max)\2; sc=S(k); if(abs(sc-n) <= sqrtint(n), break); if(sc > n, max=k-1, if(sc < n, min=k+1, break))); while(!issquarefree(k), k-=1); while(sc != n, my(j=1); if(sc > n, j = -1); k += j; sc += j; while(!issquarefree(k), k += j)); k; \\ Daniel Suteu, Jul 07 2022
(PARI) first(n)=my(v=vector(n), i); forsquarefree(k=1, if(n<268293, (33*n+30)\20, (n*Pi^2/6+0.058377*sqrt(n))\1), if(i++>n, return(v)); v[i]=k[1]); v \\ Charles R Greathouse IV, Jan 10 2023
(Haskell)
a005117 n = a005117_list !! (n-1)
a005117_list = filter ((== 1) . a008966) [1..]
(Python)
from sympy.ntheory.factor_ import core
def ok(n): return core(n, 2) == n
(Python)
from itertools import count, islice
from sympy import factorint
def A005117_gen(startvalue=1): # generator of terms >= startvalue
return filter(lambda n:all(x == 1 for x in factorint(n).values()), count(max(startvalue, 1)))
|
|
|
CROSSREFS
|
Cf. A076259 (first differences), A173143 (partial sums), A000688, A003277, A013928, A020753, A020754, A020755, A030059, A030229, A033197, A034444, A039956, A048672, A053797, A057918, A059956, A071403, A072284, A120992, A133466, A136742, A136743, A160764, A243289, A243347, A243348, A243351, A215366, A046660, A265668, A265675.
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000796
|
|
Decimal expansion of Pi (or digits of Pi).
(Formerly M2218 N0880)
|
|
+10
1006
|
|
|
|
3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 4, 5, 9, 2, 3, 0, 7, 8, 1, 6, 4, 0, 6, 2, 8, 6, 2, 0, 8, 9, 9, 8, 6, 2, 8, 0, 3, 4, 8, 2, 5, 3, 4, 2, 1, 1, 7, 0, 6, 7, 9, 8, 2, 1, 4
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Sometimes called Archimedes's constant.
Ratio of a circle's circumference to its diameter.
Also area of a circle with radius 1.
Also surface area of a sphere with diameter 1.
A useful mnemonic for remembering the first few terms: How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics ...
Also ratio of surface area of sphere to one of the faces of the circumscribed cube. Also ratio of volume of a sphere to one of the six inscribed pyramids in the circumscribed cube. - Omar E. Pol, Aug 09 2012
Also surface area of a quarter of a sphere of radius 1. - Omar E. Pol, Oct 03 2013
Also the area under the peak-shaped even function f(x)=1/cosh(x). Proof: for the upper half of the integral, write f(x) = (2*exp(-x))/(1+exp(-2x)) = 2*Sum_{k>=0} (-1)^k*exp(-(2k+1)*x) and integrate term by term from zero to infinity. The result is twice the Gregory series for Pi/4. - Stanislav Sykora, Oct 31 2013
A curiosity: a 144 X 144 magic square of 7th powers was recently constructed by Toshihiro Shirakawa. The magic sum = 3141592653589793238462643383279502884197169399375105, which is the concatenation of the first 52 digits of Pi. See the MultiMagic Squares link for details. - Christian Boyer, Dec 13 2013 [Comment revised by N. J. A. Sloane, Aug 27 2014]
x*Pi is also the surface area of a sphere whose diameter equals the square root of x. - Omar E. Pol, Dec 25 2013
Also diameter of a sphere whose surface area equals the volume of the circumscribed cube. - Omar E. Pol, Jan 13 2014
An interesting anecdote about the base-10 representation of Pi, with 3 (integer part) as first (index 1) digit:
358 0
359 3
360 6
361 0
362 0
And the circle is customarily subdivided into 360 degrees (although Pi radians yields half the circle)...
(End)
Sometimes referred to as Archimedes's constant, because the Greek mathematician computed lower and upper bounds of Pi by drawing regular polygons inside and outside a circle. In Germany it was called the Ludolphian number until the early 20th century after the Dutch mathematician Ludolph van Ceulen (1540-1610) who calculated up to 35 digits of Pi in the late 16th century. - Martin Renner, Sep 07 2016
As of the beginning of 2019 more than 22 trillion decimal digits of Pi are known. See the Wikipedia article "Chronology of computation of Pi". - Harvey P. Dale, Jan 23 2019
On March 14, 2019, Emma Haruka Iwao announced the calculation of 31.4 trillion digits of Pi using Google Cloud's infrastructure. - David Radcliffe, Apr 10 2019
Also volume of three quarters of a sphere of radius 1. - Omar E. Pol, Aug 16 2019
On August 5, 2021, researchers from the University of Applied Sciences of the Grisons in Switzerland announced they had calculated 62.8 trillion digits. Guinness World Records has not verified this yet. - Alonso del Arte, Aug 23 2021
The Hermite-Lindemann (1882) theorem states, that if z is a nonzero algebraic number, then e^z is a transcendent number. The transcendence of Pi then results from Euler's relation: e^(i*Pi) = -1. - Peter Luschny, Jul 21 2023
|
|
|
REFERENCES
|
Mohammad K. Azarian, A Summary of Mathematical Works of Ghiyath ud-din Jamshid Kashani, Journal of Recreational Mathematics, Vol. 29(1), pp. 32-42, 1998.
J. Arndt & C. Haenel, Pi Unleashed, Springer NY 2001.
P. Beckmann, A History of Pi, Golem Press, Boulder, CO, 1977.
J.-P. Delahaye, Le fascinant nombre pi, Pour la Science, Paris 1997.
P. Eyard and J.-P. Lafon, The Number Pi, Amer. Math. Soc., 2004.
S. R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, Section 1.4.
Le Petit Archimede, Special Issue On Pi, Supplement to No. 64-5, May 1980 ADCS Amiens.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 31.
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).
|
|
|
LINKS
|
J. M. Borwein and M. Macklem, The (Digital) Life of Pi, The Australian Mathematical Society Gazette, Volume 33, Number 5, Sept. 2006, pp. 243-248.
Eric Weisstein's World of Mathematics, Pi and Pi Digits
|
|
|
FORMULA
|
Pi = 4*Sum_{k>=0} (-1)^k/(2k+1) [Madhava-Gregory-Leibniz, 1450-1671]. - N. J. A. Sloane, Feb 27 2013
2/Pi = (sqrt(2)/2) * (sqrt(2 + sqrt(2))/2) * (sqrt(2 + sqrt(2 + sqrt(2)))/2) * ... [Viete, 1593]
2/Pi = Product_{k>=1} (4*k^2-1)/(4*k^2). [Wallis, 1655]
Pi = 3*sqrt(3)/4 + 24*(1/12 - Sum_{n>=2} (2*n-2)!/((n-1)!^2*(2*n-3)*(2*n+1)*2^(4*n-2))). [Newton, 1666]
Pi/4 = 4*arctan(1/5) - arctan(1/239). [Machin, 1706]
Pi^2/6 = 3*Sum_{n>=1} 1/(n^2*binomial(2*n,n)). [Euler, 1748]
1/Pi = (2*sqrt(2)/9801) * Sum_{n>=0} (4*n)!*(1103+26390*n)/((n!)^4*396^(4*n)). [Ramanujan, 1914]
1/Pi = 12*Sum_{n>=0} (-1)^n*(6*n)!*(13591409 + 545140134*n)/((3*n)!*(n!)^3*(640320^3)^(n+1/2)). [David and Gregory Chudnovsky, 1989]
Pi = Sum_{n>=0} (1/16^n) * (4/(8*n+1) - 2/(8*n+4) - 1/(8*n+5) - 1/(8*n+6)). [Bailey-Borwein-Plouffe, 1989] (End)
Pi - 2 = 1/1 + 1/3 - 1/6 - 1/10 + 1/15 + 1/21 - 1/28 - 1/36 + 1/45 + ... [Jonas Castillo Toloza, 2007], that is, Pi - 2 = Sum_{n>=1} (1/((-1)^floor((n-1)/2)*(n^2+n)/2)). - José de Jesús Camacho Medina, Jan 20 2014
Pi = 3 * Product_{t=img(r),r=(1/2+i*t) root of zeta function} (9+4*t^2)/(1+4*t^2) <=> RH is true. - Dimitris Valianatos, May 05 2016
Pi = Sum_{k>=1} (3^k - 1)*zeta(k+1)/4^k.
Pi = 2*Product_{k>=2} sec(Pi/2^k).
Pi = 2*Integral_{x>=0} sin(x)/x dx. (End)
Pi = 2^{k + 1}*arctan(sqrt(2 - a_{k - 1})/a_k) at k >= 2, where a_k = sqrt(2 + a_{k - 1}) and a_1 = sqrt(2). - Sanjar Abrarov, Feb 07 2017
Pi = lim_{n->infinity} 2/n * Sum_{m=1,n} ( sqrt( (n+1)^2 - m^2 ) - sqrt( n^2 - m^2 ) ). - Dimitri Papadopoulos, May 31 2019
Pi = Sum_{n >= 0} 2^(n+1)/( binomial(2*n,n)*(2*n + 1) ) - Euler.
More generally, Pi = (4^x)*x!/(2*x)! * Sum_{n >= 0} 2^(n+1)*(n+x)!*(n+2*x)!/(2*n+2*x+1)! = 2*4^x*x!^2/(2*x+1)! * hypergeom([2*x+1,1], [x+3/2], 1/2), valid for complex x not in {-1,-3/2,-2,-5/2,...}. Here, x! is shorthand notation for the function Gamma(x+1). This identity may be proved using Gauss's second summation theorem.
Setting x = 3/4 and x = -1/4 (resp. x = 1/4 and x = -3/4) in the above identity leads to series representations for the constant A085565 (resp. A076390). (End)
Equals 2 + Integral_{x=0..1} arccos(x)^2 dx.
Equals Integral_{x=0..oo} log(1 + 1/x^2) dx.
Equals Integral_{x=0..oo} log(1 + x^2)/x^2 dx.
Equals Integral_{x=-oo..oo} exp(x/2)/(exp(x) + 1) dx. (End)
Pi = 32*Sum_{n >= 1} (-1)^n*n^2/((4*n^2 - 1)*(4*n^2 - 9))= 384*Sum_{n >= 1} (-1)^(n+1)*n^2/((4*n^2 - 1)*(4*n^2 - 9)*(4*n^2 - 25)).
More generally, it appears that for k = 1,2,3,..., Pi = 16*(2*k)!*Sum_{n >= 1} (-1)^(n+k+1)*n^2/((4*n^2 - 1)* ... *(4*n^2 - (2*k+1)^2)).
Pi = 32*Sum_{n >= 1} (-1)^(n+1)*n^2/(4*n^2 - 1)^2 = 768*Sum_{n >= 1} (-1)^(n+1)*n^2/((4*n^2 - 1)^2*(4*n^2 - 9)^2).
More generally, it appears that for k = 0,1,2,..., Pi = 16*Catalan(k)*(2*k)!*(2*k+2)!*Sum_{n >= 1} (-1)^(n+1)*n^2/((4*n^2 - 1)^2* ... *(4*n^2 - (2*k+1)^2)^2).
Pi = (2^8)*Sum_{n >= 1} (-1)^(n+1)*n^2/(4*n^2 - 1)^4 = (2^17)*(3^5)*Sum_{n >= 2} (-1)^n*n^2*(n^2 - 1)/((4*n^2 - 1)^4*(4*n^2 - 9)^4) = (2^27)*(3^5)*(5^5)* Sum_{n >= 3} (-1)^(n+1)*n^2*(n^2 - 1)*(n^2 - 4)/((4*n^2 - 1)^4*(4*n^2 - 9)^4*(4*n^2 - 25)^4). (End)
Pi = 4/phi + Sum_{n >= 0} (1/phi^(12*n)) * ( 8/((12*n+3)*phi^3) + 4/((12*n+5)*phi^5) - 4/((12*n+7)*phi^7) - 8/((12*n+9)*phi^9) - 4/((12*n+11)*phi^11) + 4/((12*n+13)*phi^13) ) where phi = (1+sqrt(5))/2. - Chittaranjan Pardeshi, May 16 2022
Pi = 48*Sum_{n >= 0} (-1)^n/((6*n + 1)*(6*n + 3)*(6*n + 5)).
More generally, it appears that for k >= 0 we have Pi = A(k) + B(k)*Sum_{n >= 0} (-1)^n/((6*n + 1)*(6*n + 3)*...*(6*n + 6*k + 5)), where A(k) is a rational approximation to Pi and B(k) = (3 * 2^(3*k+3) * (3*k + 2)!) / (2^(3*k+1) - (-1)^k). The first few values of A(k) for k >= 0 are [0, 256/85, 65536/20955, 821559296/261636375, 6308233216/2008080987, 908209489444864/289093830828075, ...].
Pi = 16/5 - (288/5)*Sum_{n >= 0} (-1)^n * (6*n + 1)/((6*n + 1)*(6*n + 3)*...*(6*n + 9)).
More generally, it appears that for k >= 0 we have Pi = C(k) + D(k)*Sum_{n >= 0} (-1)^n* (6*n + 1)/((6*n + 1)*(6*n + 3)*...*(6*n + 6*k + 3)), where C(k) and D(k) are rational numbers. The case k = 0 is the Madhava-Gregory-Leibniz series for Pi.
Pi = 168/53 + (288/53)*Sum_{n >= 0} (-1)^n * (42*n^2 + 25*n)/((6*n + 1)*(6*n + 3)*(6*n + 5)*(6*n + 7)).
More generally, it appears that for k >= 1 we have Pi = E(k) + F(k)*Sum_{n >= 0} (-1)^n * (6*(6*k + 1)*n^2 + (24*k + 1)*n)/((6*n + 1)*(6*n + 3)*...*(6*n + 6*k + 1)), where E(k) and F(k) are rational numbers. (End)
The series representation Pi = 4 * Sum_{k >= 0} 1/(4*k + 1) - 1/(4*k + 3) given above by Alexander R. Povolotsky, Dec 25 2008, is the case n = 0 of the more general result (obtained by the WZ method): for n >= 0, there holds
Pi = Sum_{j = 0.. n-1} 2^(j+1)/((2*j + 1)*binomial(2*j,j)) + 8*(n+1)!*Sum_{k >= 0} 1/((4*k + 1)*(4*k + 3)*...*(4*k + 2*n + 3)).
Letting n -> oo gives the rapidly converging series Pi = Sum_{j >= 0} 2^(j+1)/((2*j + 1)*binomial(2*j,j)) due to Euler.
More generally, it appears that for n >= 1, Pi = 1/(2*n-1)!!^2 * Sum_{j >= 0} (Product_{i = 0..2*n-1} j - i) * 2^(j+1)/((2*j + 1)*binomial(2*j,j)).
For any integer n, Pi = (-1)^n * 4 * Sum_{k >= 0} 1/(4*k + 1 + 2*n) - 1/(4*k + 3 - 2*n). (End)
|
|
|
EXAMPLE
|
3.1415926535897932384626433832795028841971693993751058209749445923078164062\
862089986280348253421170679821480865132823066470938446095505822317253594081\
284811174502841027019385211055596446229489549303819...
|
|
|
MAPLE
|
Digits := 110: Pi*10^104:
ListTools:-Reverse(convert(floor(%), base, 10)); # Peter Luschny, Oct 29 2019
|
|
|
MATHEMATICA
|
RealDigits[ N[ Pi, 105]] [[1]]
Table[ResourceFunction["NthDigit"][Pi, n], {n, 1, 102}] (* Joan Ludevid, Jun 22 2022; easy to compute a(10000000)=7 with this function; requires Mathematica 12.0+ *)
|
|
|
PROG
|
(Macsyma) py(x) := if equal(6, 6+x^2) then 2*x else (py(x:x/3), 3*%%-4*(%%-x)^3); py(3.); py(dfloat(%)); block([bfprecision:35], py(bfloat(%))) /* Bill Gosper, Sep 09 2002 */
(PARI) { default(realprecision, 20080); x=Pi; for (n=1, 20000, d=floor(x); x=(x-d)*10; write("b000796.txt", n, " ", d)); } \\ Harry J. Smith, Apr 15 2009
(PARI) A796=[]; A000796(n)={if(n>#A796, localprec(n*6\5+29); A796=digits(Pi\.1^(precision(Pi)-3))); A796[n]} \\ NOTE: as the other programs, this returns the n-th term of the sequence, with n = 1, 2, 3, ... and not n = 1, 0, -1, -2, .... - M. F. Hasler, Jun 21 2022
(PARI) first(n)= default(realprecision, n+10); digits(floor(Pi*10^(n-1))) \\ David A. Corneth, Jun 21 2022
(Haskell) -- see link: Literate Programs
import Data.Char (digitToInt)
a000796 n = a000796_list (n + 1) !! (n + 1)
a000796_list len = map digitToInt $ show $ machin' `div` (10 ^ 10) where
machin' = 4 * (4 * arccot 5 unity - arccot 239 unity)
unity = 10 ^ (len + 10)
arccot x unity = arccot' x unity 0 (unity `div` x) 1 1 where
arccot' x unity summa xpow n sign
| term == 0 = summa
| otherwise = arccot'
x unity (summa + sign * term) (xpow `div` x ^ 2) (n + 2) (- sign)
where term = xpow `div` n
(Haskell) -- See Niemeijer link and also Gibbons link.
a000796 n = a000796_list !! (n-1) :: Int
a000796_list = map fromInteger $ piStream (1, 0, 1)
[(n, a*d, d) | (n, d, a) <- map (\k -> (k, 2 * k + 1, 2)) [1..]] where
piStream z xs'@(x:xs)
| lb /= approx z 4 = piStream (mult z x) xs
| otherwise = lb : piStream (mult (10, -10 * lb, 1) z) xs'
where lb = approx z 3
approx (a, b, c) n = div (a * n + b) c
mult (a, b, c) (d, e, f) = (a * d, a * e + b * f, c * f)
(Magma) pi:=Pi(RealField(110)); Reverse(Intseq(Floor(10^105*pi))); // Bruno Berselli, Mar 12 2013
(Python) from sympy import pi, N; print(N(pi, 1000)) # David Radcliffe, Apr 10 2019
(Python)
from mpmath import mp
if n >= len(A000796.str): mp.dps = n*6//5+50; A000796.str = str(mp.pi-5/mp.mpf(10)**mp.dps)
return int(A000796.str[n if n>1 else 0])
(SageMath)
m=125
x=numerical_approx(pi, digits=m+5)
a=[ZZ(i) for i in x.str(skip_zeroes=True) if i.isdigit()]
|
|
|
CROSSREFS
|
Pi in base b: A004601 (b=2), A004602 (b=3), A004603 (b=4), A004604 (b=5), A004605 (b=6), A004606 (b=7), A006941 (b=8), A004608 (b=9), this sequence (b=10), A068436 (b=11), A068437 (b=12), A068438 (b=13), A068439 (b=14), A068440 (b=15), A062964 (b=16), A224750 (b=26), A224751 (b=27), A060707 (b=60). - _Jason Kimberley_, Dec 06 2012
Decimal expansions of expressions involving Pi: A002388 (Pi^2), A003881 (Pi/4), A013661 (Pi^2/6), A019692 (2*Pi=tau), A019727 (sqrt(2*Pi)), A059956 (6/Pi^2), A060294 (2/Pi), A091925 (Pi^3), A092425 (Pi^4), A092731 (Pi^5), A092732 (Pi^6), A092735 (Pi^7), A092736 (Pi^8), A163973 (Pi/log(2)).
Cf. A001901 (Pi/2; Wallis), A002736 (Pi^2/18; Euler), A007514 (Pi), A048581 (Pi; BBP), A054387 (Pi; Newton), A092798 (Pi/2), A096954 (Pi/4; Machin), A097486 (Pi), A122214 (Pi/2), A133766 (Pi/4 - 1/2), A133767 (5/6 - Pi/4), A166107 (Pi; MGL).
|
|
|
KEYWORD
|
cons,nonn,nice,core,easy,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000007
|
|
The characteristic function of {0}: a(n) = 0^n.
(Formerly M0002)
|
|
+10
1003
|
|
|
|
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
Changing the offset to 1 gives the arithmetical function a(1) = 1, a(n) = 0 for n > 1, the identity function for Dirichlet multiplication (see Apostol). - N. J. A. Sloane
Changing the offset to 1 makes this the decimal expansion of 1. - N. J. A. Sloane, Nov 13 2014
Hankel transform (see A001906 for definition) of A000007 (powers of 0), A000012 (powers of 1), A000079 (powers of 2), A000244 (powers of 3), A000302 (powers of 4), A000351 (powers of 5), A000400 (powers of 6), A000420 (powers of 7), A001018 (powers of 8), A001019 (powers of 9), A011557 (powers of 10), A001020 (powers of 11), etc. - Philippe Deléham, Jul 07 2005
This is the identity sequence with respect to convolution. - David W. Wilson, Oct 30 2006
The alternating sum of the n-th row of Pascal's triangle gives the characteristic function of 0, a(n) = 0^n. - Daniel Forgues, May 25 2010
The number of maximal self-avoiding walks from the NW to SW corners of a 1 X n grid. - Sean A. Irvine, Nov 19 2010
Historically there has been some disagreement as to whether 0^0 = 1. Graphing x^0 seems to support that conclusion, but graphing 0^x instead suggests that 0^0 = 0. Euler and Knuth have argued in favor of 0^0 = 1. For some calculators, 0^0 triggers an error, while in Mathematica, 0^0 is Indeterminate. - Alonso del Arte, Nov 15 2011
Another consequence of changing the offset to 1 is that then this sequence can be described as the sum of Moebius mu(d) for the divisors d of n. - Alonso del Arte, Nov 28 2011
With the convention 0^0 = 1, 0^n = 0 for n > 0, the sequence a(n) = 0^|n-k|, which equals 1 when n = k and is 0 for n >= 0, has g.f. x^k. A000007 is the case k = 0. - George F. Johnson, Mar 08 2013
A fixed point of the run length transform. - Chai Wah Wu, Oct 21 2016
|
|
|
REFERENCES
|
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 30.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
|
|
|
LINKS
|
|
|
|
FORMULA
|
As a function of Bernoulli numbers (cf. A027641: (1, -1/2, 1/6, 0, -1/30, ...)), triangle A074909 (the beheaded Pascal's triangle) * B_n as a vector = [1, 0, 0, 0, 0, ...]. - Gary W. Adamson, Mar 05 2012
a(n) = Sum_{k = 0..n} exp(2*Pi*i*k/(n+1)) is the sum of the (n+1)th roots of unity. - Franz Vrabec, Nov 09 2012
Inverse binomial transform of A000012. (End)
|
|
|
MAPLE
|
A000007 := proc(n) if n = 0 then 1 else 0 fi end: seq(A000007(n), n=0..20);
spec := [A, {A=Z} ]: seq(combstruct[count](spec, size=n+1), n=0..20);
|
|
|
MATHEMATICA
|
Table[If[n == 0, 1, 0], {n, 0, 99}]
Table[Boole[n == 0], {n, 0, 99}] (* Michael Somos, Aug 25 2012 *)
Join[{1}, LinearRecurrence[{1}, {0}, 102]] (* Ray Chandler, Jul 30 2015 *)
|
|
|
PROG
|
(PARI) {a(n) = !n};
(Magma) [1] cat [0:n in [1..100]]; // Sergei Haller, Dec 21 2006
(Haskell)
a000007 = (0 ^)
a000007_list = 1 : repeat 0
(Python)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000961
|
|
Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).
(Formerly M0517 N0185)
|
|
+10
943
|
|
|
|
1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.)
These numbers are (apart from 1) the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004
Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - Amarnath Murthy, Jan 09 2002
These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - Mats Granvik, Nov 18 2007
These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (=A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - M. F. Hasler, Jan 18 2007, Apr 18 2010
Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - M. F. Hasler, Apr 04 2008
Also, {A138929(k) ; k>1} = {2*A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - M. F. Hasler, Apr 04 2008
Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - Juri-Stepan Gerasimov, Dec 09 2009, Mar 10 2010
The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - W. Edwin Clark, Aug 05 2014
Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - Michel Marcus, Jan 16 2019
Possible numbers of elements in a finite vector space. - Jianing Song, Apr 22 2021
|
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
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).
|
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
|
|
|
FORMULA
|
Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - N. J. A. Sloane, Oct 31 2014, corrected by M. F. Hasler, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).]
m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)=A019434(k) or a(n)=A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - M. F. Hasler, Jan 18 2007, Apr 18 2010
|
|
|
MAPLE
|
readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d, `, n) fi: od:
# second Maple program:
a:= proc(n) option remember; local k; for k from
1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
|
|
|
MATHEMATICA
|
Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski *)
|
|
|
PROG
|
(Magma) [1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by Arkadiusz Wesolowski, Jul 20 2012
(PARI) A000961(n, l=-1, k=0)=until(n--<1, until(l<lcm(l, k++), ); l=lcm(l, k)); k
print_A000961(lim=999, l=-1)=for(k=1, lim, l==lcm(l, k) && next; l=lcm(l, k); print1(k, ", ")) \\ M. F. Hasler, Jan 18 2007
(PARI) nextA000961(n)=my(m, r, p); m=2*n; for(e=1, ceil(log(n+0.01)/log(2)), r=(n+0.01)^(1/e); p=prime(primepi(r)+1); m=min(m, p^e)); m \\ Michael B. Porter, Nov 02 2009
(PARI) list(lim)=my(v=primes(primepi(lim)), u=List([1])); forprime(p=2, sqrtint(lim\1), for(e=2, log(lim+.5)\log(p), listput(u, p^e))); vecsort(concat(v, Vec(u))) \\ Charles R Greathouse IV, Nov 20 2012
(Haskell)
import Data.Set (singleton, deleteFindMin, insert)
a000961 n = a000961_list !! (n-1)
a000961_list = 1 : g (singleton 2) (tail a000040_list) where
g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
where (m, s') = deleteFindMin s
(Sage)
R = [1]
for i in (2..n):
if i.is_prime_power(): R.append(i)
return R
(Python)
from sympy import primerange
def A000961_list(limit): # following Python style, list terms < limit
L = [1]
for p in primerange(1, limit):
pe = p
while pe < limit:
L.append(pe)
pe *= p
|
|
|
CROSSREFS
|
There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Complementary (in the positive integers) to sequence A024619. - _Jason Kimberley_, Nov 10 2015
|
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A002808
|
|
The composite numbers: numbers n of the form x*y for x > 1 and y > 1.
(Formerly M3272 N1322)
|
|
+10
932
|
|
|
|
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The natural numbers 1,2,... are divided into three sets: 1 (the unit), the primes (A000040) and the composite numbers (A002808).
The number of composite numbers <= n (A065855) = n - pi(n) (A000720) - 1.
n is composite iff sigma(n) + phi(n) > 2n. This is a nice result of the well known theorem: For all positive integers n, n = Sum_{d|n} phi(d). For the proof see my contribution to puzzle 76 of Carlos Rivera's Primepuzzles. - Farideh Firoozbakht, Jan 27 2005, Jan 18 2015
The composite numbers have the semiprimes A001358 as primitive elements.
Composite numbers n which are the product of r=A001222(n) prime numbers are sometimes called r-almost primes. Sequences listing r-almost primes are: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20). - _Jason Kimberley_, Oct 02 2011
Degrees for which there are irreducible polynomials which are reducible mod p for all primes p, see Brandl. - Charles R Greathouse IV, Sep 04 2014
An integer is composite if and only if it is the sum of strictly positive integers in arithmetic progression with common difference 2: 4 = 1 + 3, 6 = 2 + 4, 8 = 3 + 5, 9 = 1 + 3 + 5, etc. - Jean-Christophe Hervé, Oct 02 2014
This statement holds since k+(k+2)+...+k+2(n-1) = n*(n+k-1) = a*b with arbitrary a,b (taking n=a and k=b-a+1 if b>=a). - M. F. Hasler, Oct 04 2014
For n > 4, these are numbers n such that n!/n^2 = (n-1)!/n is an integer (see A056653). - Derek Orr, Apr 16 2015
Let f(x) = Sum_{i=1..x} Sum_{j=2..i-1} cos((2*Pi*x*j)/i). It is known that the zeros of f(x) are the prime numbers. So these are the numbers n such that f(n) > 0. - Michel Lagneau, Oct 13 2015
Numbers n that can be written as solutions of the Diophantine equation n = (x+2)(y+2) where {x,y} in N^2, pairs of natural numbers including zero (cf. Mathematica code and Davis). - Ron R Spencer and Bradley Klee, Aug 15 2016
Numbers n with a partition (containing at least two summands) so that its summands also multiply to n. If n is prime, there is no way to find those two (or more) summands. If n is composite, simply take a factor or several, write those divisors and fill with enough 1's so that they add up to n. For example: 4 = 2*2 = 2+2, 6 = 1*2*3 = 1+2+3, 8 = 1*1*2*4 = 1+1+2+4, 9 = 1*1*1*3*3 = 1+1+1+3+3. - Juhani Heino, Aug 02 2017
|
|
|
REFERENCES
|
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
A. E. Bojarincev, Asymptotic expressions for the n-th composite number, Univ. Mat. Zap. 6:21-43 (1967). - In Russian.
Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 66.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 51.
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = pi(a(n)) + 1 + n, where pi is the prime counting function.
n + n/log n + n/log^2 n < a(n) < n + n/log n + 3n/log^2 n for n >= 4, see Panaitopol. Bojarincev gives an asymptotic version. - Charles R Greathouse IV, Oct 23 2012
a(n) = 1 + a(n-1) + f(n) for n > 1 with a(1) = 4 where f(n) = 1 if n belongs to A014689, 0 otherwise. - Mikhail Kurkov, Dec 21 2021
|
|
|
MAPLE
|
t := []: for n from 2 to 20000 do if isprime(n) then else t := [op(t), n]; fi; od: t; remove(isprime, [$3..89]); # Zerinvary Lajos, Mar 19 2007
A002808 := proc(n) option remember ; local a ; if n = 1 then 4; else for a from procname(n-1)+1 do if not isprime(a) then return a; end if; end do ; end if; end proc; # R. J. Mathar, Oct 27 2009
|
|
|
MATHEMATICA
|
Select[Range[2, 100], !PrimeQ[#]&] (* Zak Seidov, Mar 05 2011 *)
With[{nn=100}, Complement[Range[nn], Prime[Range[PrimePi[nn]]]]] (* Harvey P. Dale, May 01 2012 *)
|
|
|
PROG
|
(PARI) A002808(n)= my(k=-1); while( -n + n += -k + k=primepi(n), ); n \\ For n=10^4 resp. 3*10^4, this is about 100 resp. 500 times faster than the former; M. F. Hasler, Nov 11 2009
(PARI) forcomposite(n=1, 1e2, print1(n, ", ")) \\ Felix Fröhlich, Aug 03 2014
(PARI) for(n=1, 1e3, if(bigomega(n) > 1, print1(n, ", "))) \\ Altug Alkan, Oct 14 2015
(Haskell)
a002808 n = a002808_list !! (n-1)
a002808_list = filter ((== 1) . a066247) [2..]
(Python)
from sympy import primepi
m, k = n, primepi(n) + 1 + n
while m != k:
m, k = k, primepi(k) + 1 + n
return m # Chai Wah Wu, Jul 15 2015, updated Apr 14 2016
(Python)
from sympy import isprime
def ok(n): return n > 1 and not isprime(n)
(Magma) [n: n in [2..250] | not IsPrime(n)]; // G. C. Greubel, Feb 24 2024
(SageMath) [n for n in (2..250) if not is_prime(n)] # G. C. Greubel, Feb 24 2024
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy,core
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A007814
|
|
Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.
|
|
+10
850
|
|
|
|
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. Sloane
To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003
The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ...), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003
Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004
Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014
a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006
Let F(n) be the n-th Fermat number (A000215). Then F(a(r-1)) divides F(n)+2^k for r = k mod 2^n and r != 1. - T. D. Noe, Jul 12 2007
The following relation holds: 2^A007814(n)*(2*A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009].)
a(n) is the number of 0's at the end of n when n is written in base 2.
a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0). That is, A003188(n) XOR A003188(n+1) == 2^A007814(n). - Russ Cox, Dec 04 2010
The sequence is squarefree (in the sense of not containing any subsequence of the form XX) [Allouche and Shallit]. Of course it contains individual terms that are squares (such as 4). - Comment expanded by N. J. A. Sloane, Jan 28 2019
a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011
Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - _Jason Kimberley_, Sep 09 2011
a(n) = number of 1's in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} p_j-th prime (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24)=3; indeed, the partition having Heinz number 24 = 2*2*2*3 is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015
a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - Emeric Deutsch, Aug 24 2017
Apart from being squarefree, as noted above, the sequence has the property that every consecutive subsequence contains at least one number an odd number of times. - Jon Richfield, Dec 20 2018
a(n+1) is the 2-adic valuation of Sum_{e=0..n} u^e = (1 + u + u^2 + ... + u^n), for any u of the form 4k+1 (A016813). - Antti Karttunen, Aug 15 2020
{a(n)} represents the "first black hat" strategy for the game of countably infinitely many hats, with a probability of success of 1/3; cf. the Numberphile link below. - Frederic Ruget, Jun 14 2021
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
|
|
|
LINKS
|
Giovanni Pighizzini, Limited Automata: Properties, Complexity and Variants, International Conference on Descriptional Complexity of Formal Systems (DCFS 2019) Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science (LNCS, Vol. 11612) Springer, Cham, 57-73.
|
|
|
FORMULA
|
G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Apr 10 2002
Totally additive with a(p) = 1 if p = 2, 0 otherwise.
Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007
Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0)*c(1) + c(0)*c(1)*c(2) + ... + c(0)*c(1)...c(n-1); a(k+1) = b(0) + b(0)*b(1) + b(0)*b(1)*b(2) + ... + b(0)*b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008
v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - A. Neves, Sep 28 2010, corrected Oct 04 2010
a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Feb 16 2019
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Jul 11 2020
a(n) = 2*Sum_{j=1..floor(log_2(n))} frac(binomial(n, 2^j)*2^(j-1)/n). - Dario T. de Castro, Jul 08 2022
a(n) = floor((gcd(n, 2^n)^(n+1) mod (2^(n+1)-1)^2)/(2^(n+1)-1)) (see Lemma 3.4 from Mazzanti's 2002 article). - Lorenzo Sauras Altuzarra, Mar 10 2024
|
|
|
EXAMPLE
|
2^3 divides 24, so a(24)=3.
Triangle begins:
0;
1,0;
2,0,1,0;
3,0,1,0,2,0,1,0;
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,...
(End)
|
|
|
MAPLE
|
ord := proc(n) local i, j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111);
|
|
|
MATHEMATICA
|
p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]
DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *)
Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)
Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *)
|
|
|
PROG
|
(Haskell)
a007814 n = if m == 0 then 1 + a007814 n' else 0
where (n', m) = divMod n 2
(Haskell)
a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
(Magma) [Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013
(Python)
import math
def a(n): return int(math.log(n - (n & n - 1), 2)) # Indranil Ghosh, Apr 18 2017
(Python)
(Scheme) (define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A005843
|
|
The nonnegative even numbers: a(n) = 2n.
(Formerly M0985)
|
|
+10
720
|
|
|
|
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
-2, -4, -6, -8, -10, -12, -14, ... are the trivial zeros of the Riemann zeta function. - Vivek Suri (vsuri(AT)jhu.edu), Jan 24 2008
If a 2-set Y and an (n-2)-set Z are disjoint subsets of an n-set X then a(n-2) is the number of 2-subsets of X intersecting both Y and Z. - Milan Janjic, Sep 19 2007
Omitting the initial zero gives the number of prime divisors with multiplicity of product of terms of n-th row of A077553. - Ray Chandler, Aug 21 2003
The number of hydrogen atoms in straight-chain (C(n)H(2n+2)), branched (C(n)H(2n+2), n > 3), and cyclic, n-carbon alkanes (C(n)H(2n), n > 2). - Paul Muljadi, Feb 18 2010
For n >= 1; a(n) = the smallest numbers m with the number of steps n of iterations of {r - (smallest prime divisor of r)} needed to reach 0 starting at r = m. See A175126 and A175127. A175126(a(n)) = A175126(A175127(n)) = n. Example (a(4)=8): 8-2=6, 6-2=4, 4-2=2, 2-2=0; iterations has 4 steps and number 8 is the smallest number with such result. - Jaroslav Krizek, Feb 15 2010
a(k) is the (Moore lower bound on and the) order of the (k,4)-cage: the smallest k-regular graph having girth four: the complete bipartite graph with k vertices in each part. - _Jason Kimberley_, Oct 30 2011
Let n be the number of pancakes that have to be divided equally between n+1 children. a(n) is the minimal number of radial cuts needed to accomplish the task. - Ivan N. Ianakiev, Sep 18 2013
For n > 0, a(n) is the largest number k such that (k!-n)/(k-n) is an integer. - Derek Orr, Jul 02 2014
a(n) when n > 2 is also the number of permutations simultaneously avoiding 213, 231 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl Aug 07 2014
It appears that for n > 2, a(n) = A020482(n) + A002373(n), where all sequences are infinite. This is consistent with Goldbach's conjecture, which states that every even number > 2 can be expressed as the sum of two prime numbers. - Bob Selcoe, Mar 08 2015
Number of partitions of 4n into exactly 2 parts. - Colin Barker, Mar 23 2015
Number of neighbors in von Neumann neighborhood. - Dmitry Zaitsev, Nov 30 2015
Unique solution b( ) of the complementary equation a(n) = a(n-1)^2 - a(n-2)*b(n-1), where a(0) = 1, a(1) = 3, and a( ) and b( ) are increasing complementary sequences. - Clark Kimberling, Nov 21 2017
Also the maximum number of non-attacking bishops on an (n+1) X (n+1) board (n>0). (Cf. A000027 for rooks and queens (n>3), A008794 for kings or A030978 for knights.) - Martin Renner, Jan 26 2020
Integer k is even positive iff phi(2k) > phi(k), where phi is Euler's totient (A000010) [see reference De Koninck & Mercier]. - Bernard Schott, Dec 10 2020
Number of 3-permutations of n elements avoiding the patterns 132, 213, 312 and also number of 3-permutations avoiding the patterns 213, 231, 321. See Bonichon and Sun. - Michel Marcus, Aug 20 2022
|
|
|
REFERENCES
|
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
J.-M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 529a pp. 71 and 257, Ellipses, 2004, Paris.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: 2*x/(1-x)^2.
G.f. with interpolated zeros: 2x^2/((1-x)^2 * (1+x)^2); e.g.f. with interpolated zeros: x*sinh(x). - Geoffrey Critzer, Aug 25 2012
Digit sequence 22 read in base n-1. - _Jason Kimberley_, Oct 30 2011
a(n) = 2*n = Product_{k=1..2*n-1} 2*sin(Pi*k/(2*n)), n >= 0 (undefined product := 1). See an Oct 09 2013 formula contribution in A000027 with a reference. - Wolfdieter Lang, Oct 10 2013
Sum_{n>=1} (-1)^(n+1)/a(n) = log(2)/2 = (1/2)*A002162 = (1/10)*A016655. (End)
Sum_{n>=1} 1/a(n)^2 = Pi^2/24 = A222171.
Sum_{n>=1} (-1)^(n+1)/a(n)^2 = Pi^2/48 = A245058. (End)
|
|
|
EXAMPLE
|
G.f. = 2*x + 4*x^2 + 6*x^3 + 8*x^4 + 10*x^5 + 12*x^6 + 14*x^7 + 16*x^8 + ...
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(Magma) [ 2*n : n in [0..100]];
(R) seq(0, 200, 2)
(Haskell)
a005843 = (* 2)
|
|
|
CROSSREFS
|
Cf. A000027, A002061, A005408, A001358, A077553, A077554, A077555, A002024, A087112, A157888, A157889, A140811, A157872, A157909, A157910, A165900.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), this sequence (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - _Jason Kimberley_, Oct 30 2011
Cf. A231200 (boustrophedon transform).
|
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.435 seconds
|
