Search: forgues
|
| |
|
|
A000040
|
|
The prime numbers.
(Formerly M0652 N0241)
|
|
+10
10564
|
|
|
|
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
See A065091 for comments, formulas etc. concerning only odd primes. For all information concerning prime powers, see A000961. For contributions concerning "almost primes" see A002808.
A number p is prime if (and only if) it is greater than 1 and has no positive divisors except 1 and p.
A natural number is prime if and only if it has exactly two (positive) divisors.
A prime has exactly one proper positive divisor, 1.
The paper by Kaoru Motose starts as follows: "Let q be a prime divisor of a Mersenne number 2^p-1 where p is prime. Then p is the order of 2 (mod q). Thus p is a divisor of q - 1 and q > p. This shows that there exist infinitely many prime numbers." - Pieter Moree, Oct 14 2004
1 is not a prime, for if the primes included 1, then the factorization of a natural number n into a product of primes would not be unique, since n = n*1.
Prime(n) and pi(n) are inverse functions: A000720(a(n)) = n and a(n) is the least number m such that a(A000720(m)) = a(n). a(A000720(n)) = n if (and only if) n is prime.
Second sequence ever computed by electronic computer, on EDSAC, May 09 1949 (see Renwick link). - Russ Cox, Apr 20 2006
The Greek transliteration of 'Prime Number' is 'Protos Arithmos'. - _Daniel Forgues_, May 08 2009 [Edited by Petros Hadjicostas, Nov 18 2019]
A number n is prime if and only if it is different from zero and different from a unit and each multiple of n decomposes into factors such that n divides at least one of the factors. This applies equally to the integers (where a prime has exactly four divisors (the definition of divisors is relaxed such that they can be negative)) and the positive integers (where a prime has exactly two distinct divisors). - Peter Luschny, Oct 09 2012
Motivated by his conjecture on representations of integers by alternating sums of consecutive primes, for any positive integer n, Zhi-Wei Sun conjectured that the polynomial P_n(x) = Sum_{k=0..n} a(k+1)*x^k is irreducible over the field of rational numbers with the Galois group S_n, and moreover P_n(x) is irreducible mod a(m) for some m <= n(n+1)/2. It seems that no known criterion on irreduciblity of polynomials implies this conjecture. - Zhi-Wei Sun, Mar 23 2013
Natural numbers such that there is exactly one base b such that the base-b alternate digital sum is 0 (see A239707).
Equivalently: Numbers p > 1 such that b = p-1 is the only base >= 1 for which the base-b alternate digital sum is 0.
Equivalently: Numbers p > 1 such that the base-b alternate digital sum is <> 0 for all bases 1 <= b < p-1. (End)
An integer n > 1 is a prime if and only if it is not the sum of positive integers in arithmetic progression with common difference 2. - Jean-Christophe Hervé, Jun 01 2014
Conjecture: Numbers having prime factors <= prime(n+1) are {k|k^f(n) mod primorial(n)=1}, where f(n) = lcm(prime(i)-1, i=1..n) = A058254(n) and primorial(n) = A002110(n). For example, numbers with no prime divisor <= prime(7) = 17 are {k|k^60 mod 30030=1}. - Gary Detlefs, Jun 07 2014
Cramer conjecture prime(n+1) - prime(n) < C log^2 prime(n) is equivalent to the inequality (log prime(n+1)/log prime(n))^n < e^C, as n tend to infinity, where C is an absolute constant. - Thomas Ordowski, Oct 06 2014
I conjecture that for any positive rational number r there are finitely many primes q_1,...,q_k such that r = Sum_{j=1..k} 1/(q_j-1). For example, 2 = 1/(2-1) + 1/(3-1) + 1/(5-1) + 1/(7-1) + 1/(13-1) with 2, 3, 5, 7 and 13 all prime, 1/7 = 1/(13-1) + 1/(29-1) + 1/(43-1) with 13, 29 and 43 all prime, and 5/7 = 1/(3-1) + 1/(7-1) + 1/(31-1) + 1/(71-1) with 3, 7, 31 and 71 all prime. - Zhi-Wei Sun, Sep 09 2015
I also conjecture that for any positive rational number r there are finitely many primes p_1,...,p_k such that r = Sum_{j=1..k} 1/(p_j+1). For example, 1 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(11+1) + 1/(23+1) with 2, 3, 5, 7, 11 and 23 all prime, and 10/11 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(43+1) + 1/(131+1) + 1/(263+1) with 2, 3, 5, 7, 43, 131 and 263 all prime. - Zhi-Wei Sun, Sep 13 2015
Numbers k such that ((k-2)!!)^2 == +-1 (mod k). - Thomas Ordowski, Aug 27 2016
Does not satisfy Benford's law [Diaconis, 1977; Cohen-Katz, 1984; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 07 2017
Prime numbers are the integer roots of 1 - sin(Pi*Gamma(s)/s)/sin(Pi/s). - Peter Luschny, Feb 23 2018
Conjecture: log log a(n+1) - log log a(n) < 1/n. - Thomas Ordowski, Feb 17 2023
|
|
|
REFERENCES
|
M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I, Chaps. 8, 9.
D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag NY 1989.
M. Cipolla, "La determinazione asintotica dell'n-mo numero primo.", Rend. d. R. Acc. di sc. fis. e mat. di Napoli, s. 3, VIII (1902), pp. 132-166.
R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 1.
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.
J.-P. Delahaye, Merveilleux nombres premiers, Pour la Science-Belin Paris, 2000.
J.-P. Delahaye, Savoir si un nombre est premier: facile, Pour La Science, 303(1) 2003, pp. 98-102.
Diaconis, Persi, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, 5, 1977, 72--81,
M. Dietzfelbinger, Primality Testing in Polynomial Time, Springer NY 2004.
M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 5.
J. Elie, "L'algorithme AKS", in 'Quadrature', No. 60, pp. 22-32, 2006 EDP-sciences, Les Ulis (France);
W. & F. Ellison, Prime Numbers, Hermann Paris 1985
T. Estermann, Introduction to Modern Prime Number Theory, Camb. Univ. Press, 1969.
J. M. Gandhi, Formulae for the nth prime. Proc. Washington State Univ. Conf. on Number Theory, 96-106. Wash. St. Univ., Pullman, Wash., 1971.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. (260-264).
H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035, cf. http://www.ams.org/mathscinet-getitem?mr=1336709
M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972.
D. S. Jandu, Prime Numbers And Factorization, Infinite Bandwidth Publishing, N. Hollywood CA 2007.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea, NY, 1974.
D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e
D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Chap. 6.
H. Lifchitz, Table des nombres premiers de 0 à 20 millions (Tomes I & II), Albert Blanchard, Paris 1971.
R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082, cf http://www.ams.org/mathscinet-getitem?mr=96m:11082
P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag NY 1995.
P. Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004.
H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser Boston, Cambridge MA 1994.
B. Rittaud, "31415879. Ce nombre est-il premier?" ['Is this number prime?'], La Recherche, Vol. 361, pp. 70-73, Feb 15 2003, Paris.
D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, Chap. 1.
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).
D. Wells, Prime Numbers: The Most Mysterious Figures In Math, J. Wiley NY 2005.
H. C. Williams and Jeffrey Shallit, Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143
|
|
|
LINKS
|
C. K. Caldwell and Y. Xiong, What is the smallest prime?, J. Integer Seq. 15 (2012), no. 9, Article 12.9.7 and arXiv:1209.2007 [math.HO], 2012.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. [Annotated and scanned copy]
|
|
|
FORMULA
|
The prime number theorem is the statement that a(n) ~ n * log n as n -> infinity (Hardy and Wright, page 10).
For n >= 2, n*(log n + log log n - 3/2) < a(n); for n >= 20, a(n) < n*(log n + log log n - 1/2). [Rosser and Schoenfeld]
For all n, a(n) > n log n. [Rosser]
n log(n) + n (log log n - 1) < a(n) < n log n + n log log n for n >= 6. [Dusart, quoted in the Wikipedia article]
a(n) = n log n + n log log n + (n/log n)*(log log n - log n - 2) + O( n (log log n)^2/ (log n)^2). [Cipolla, see also Cesàro or the "Prime number theorem" Wikipedia article for more terms in the expansion]
a(n) = 2 + Sum_{k = 2..floor(2n*log(n)+2)} (1-floor(pi(k)/n)), for n > 1, where the formula for pi(k) is given in A000720 (Ruiz and Sondow 2002). - Jonathan Sondow, Mar 06 2004
I conjecture that Sum_{i>=1} (1/(prime(i)*log(prime(i)))) = Pi/2 = 1.570796327...; Sum_{i=1..100000} (1/(prime(i)*log(prime(i)))) = 1.565585514... It converges very slowly. - Miklos Kristof, Feb 12 2007
The last conjecture has been discussed by the math.research newsgroup recently. The sum, which is greater than Pi/2, is shown in sequence A137245. - T. D. Noe, Jan 13 2009
Conjecture:
a(n) = {n| n! mod n^2 = n(n-1)}, n <> 4.
a(n) = {n| n!*h(n) mod n = n-1}, n <> 4, where h(n) = Sum_{k=1..n} 1/k. (End)
For n = 1..15, a(n) = p + abs(p-3/2) + 1/2, where p = m + int((m-3)/2), and m = n + int((n-2)/8) + int((n-4)/8). - Timothy Hopper, Oct 23 2010
Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(n-1) mod n = 1}. - Gary Detlefs, May 25 2014
Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(3*n) mod 3*n = 8}. - Gary Detlefs, May 28 2014
a(n) = 1 + Sum_{m=1..L(n)} (abs(n-Pi(m))-abs(n-Pi(m)-1/2)+1/2), where Pi(m) = A000720(m) and L(n) >= a(n)-1. L(n) can be any function of n which satisfies the inequality. For instance, L(n) can be ceiling((n+1)*log((n+1)*log(n+1))) since it satisfies this inequality. - Timothy Hopper, May 30 2015, Jun 16 2015
Satisfies a(n) = 2*n + Sum_{k=1..(a(n)-1)} cot(k*Pi/a(n))*sin(2*k*n^a(n)*Pi/a(n)). - Ilya Gutkovskiy, Jun 29 2016
Sum_{n>=1} 1/a(n)^s = P(s), where P(s) is the prime zeta function. - Eric W. Weisstein, Nov 08 2016
a(n) = floor(1 - log(-1/2 + Sum_{ d | A002110(n-1) } mu(d)/(2^d-1))/log(2)) where mu(d) = A008683(d). Golomb gave a proof in 1974: Give each positive integer a probability of W(n) = 1/2^n, then the probability M(d) of the integer multiple of number d equals 1/(2^d-1). Suppose Q = a(1)*a(2)*...*a(n-1) = A002110(n-1), then the probability of random integers that are mutually prime with Q is Sum_{ d | Q } mu(d)*M(d) = Sum_{ d | Q } mu(d)/(2^d-1) = Sum_{ gcd(m, Q) = 1 } W(m) = 1/2 + 1/2^a(n) + 1/2^a(n+1) + 1/2^a(n+2) + ... So ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) = 1 + x(n), which means that a(n) is the only integer so that 1 < ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) < 2. - Jinyuan Wang, Apr 08 2019
|
|
|
MAPLE
|
A000040 := n->ithprime(n); [ seq(ithprime(i), i=1..100) ];
# For illustration purposes only:
isPrime := s -> is(1 = sin(Pi*GAMMA(s)/s)/sin(Pi/s)):
|
|
|
MATHEMATICA
|
Prime[Range[60]]
|
|
|
PROG
|
(Magma) [n : n in [2..500] | IsPrime(n)];
(Magma) a := func< n | NthPrime(n) >;
(PARI) {a(n) = if( n<1, 0, prime(n))};
(PARI) /* The following functions provide asymptotic approximations, one based on the asymptotic formula cited above (slight overestimate for n > 10^8), the other one based on pi(x) ~ li(x) = Ei(log(x)) (slight underestimate): */
prime1(n)=n*(log(n)+log(log(n))-1+(log(log(n))-2)/log(n)-((log(log(n))-6)*log(log(n))+11)/log(n)^2/2)
prime2(n)=solve(X=n*log(n)/2, 2*n*log(n), real(eint1(-log(X)))+n)
(PARI) forprime(p=2, 10^3, print1(p, ", ")) \\ Felix Fröhlich, Jun 30 2014
if n = 1 then return(2),
)$ /* recursive, to be replaced if possible - R. J. Mathar, Feb 27 2012 */
(Haskell) See also Haskell Wiki Link
import Data.List (genericIndex)
a000040 n = genericIndex a000040_list (n - 1)
a000040_list = base ++ larger where
base = [2, 3, 5, 7, 11, 13, 17]
larger = p : filter prime more
prime n = all ((> 0) . mod n) $ takeWhile (\x -> x*x <= n) larger
_ : p : more = roll $ makeWheels base
roll (Wheel n rs) = [n * k + r | k <- [0..], r <- rs]
makeWheels = foldl nextSize (Wheel 1 [1])
nextSize (Wheel size bs) p = Wheel (size * p)
[r | k <- [0..p-1], b <- bs, let r = size*k+b, mod r p > 0]
data Wheel = Wheel Integer [Integer]
(GAP)
(Python)
from sympy import primerange
|
|
|
CROSSREFS
|
Cf. A003558, A179480 (relating to the Quasi-order theorem of Hilton and Pedersen).
|
|
|
KEYWORD
|
core,nonn,nice,easy,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000203
|
|
a(n) = sigma(n), the sum of the divisors of n. Also called sigma_1(n).
(Formerly M2329 N0921)
|
|
+10
4994
|
|
|
|
1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Multiplicative: If the canonical factorization of n into prime powers is the product of p^e(p) then sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1).
Sum_{d|n} 1/d^k is equal to sigma_k(n)/n^k. So sequences A017665-A017712 also give the numerators and denominators of sigma_k(n)/n^k for k = 1..24. The power sums sigma_k(n) are in sequences A000203 (this sequence) (k=1), A001157-A001160 (k=2,3,4,5), A013954-A013972 for k = 6,7,...,24. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 05 2001
A number n is abundant if sigma(n) > 2n (cf. A005101), perfect if sigma(n) = 2n (cf. A000396), deficient if sigma(n) < 2n (cf. A005100).
a(n) is the number of sublattices of index n in a generic 2-dimensional lattice. - Avi Peretz (njk(AT)netvision.net.il), Jan 29 2001 [In the language of group theory, a(n) is the number of index-n subgroups of Z x Z. - Jianing Song, Nov 05 2022]
The sublattices of index n are in one-to-one correspondence with matrices [a b; 0 d] with a>0, ad=n, b in [0..d-1]. The number of these is Sum_{d|n} d = sigma(n), which is a(n). A sublattice is primitive if gcd(a,b,d) = 1; the number of these is n * Product_{p|n} (1+1/p), which is A001615. [Cf. Grady reference.]
Sum of number of common divisors of n and m, where m runs from 1 to n. - Naohiro Nomoto, Jan 10 2004
a(n) is the cardinality of all extensions over Q_p with degree n in the algebraic closure of Q_p, where p>n. - Volker Schmitt (clamsi(AT)gmx.net), Nov 24 2004. Cf. A100976, A100977, A100978 (p-adic extensions).
Let s(n) = a(n-1) + a(n-2) - a(n-5) - a(n-7) + a(n-12) + a(n-15) - a(n-22) - a(n-26) + ..., then a(n) = s(n) if n is not pentagonal, i.e., n != (3 j^2 +- j)/2 (cf. A001318), and a(n) is instead s(n) - ((-1)^j)*n if n is pentagonal. - Gary W. Adamson, Oct 05 2008 [corrected Apr 27 2012 by William J. Keith based on Ewell and by Andrey Zabolotskiy, Apr 08 2022]
Write n as 2^k * d, where d is odd. Then a(n) is odd if and only if d is a square. - Jon Perry, Nov 08 2012
Also total number of parts in the partitions of n into equal parts. - Omar E. Pol, Jan 16 2013
Note that sigma(3^4) = 11^2. On the other hand, Kanold (1947) shows that the equation sigma(q^(p-1)) = b^p has no solutions b > 2, q prime, p odd prime. - N. J. A. Sloane, Dec 21 2013, based on postings to the Number Theory Mailing List by Vladimir Letsko and Luis H. Gallardo
Also the total number of horizontal rhombuses in the terraces of the n-th level of an irregular stepped pyramid (starting from the top) whose structure arises after the k-degree-zig-zag folding of every row of the diagram of the isosceles triangle A237593, where k is an angle greater than zero and less than 180 degrees. - Omar E. Pol, Jul 05 2016
Equivalent to the Riemann hypothesis: a(n) < H(n) + exp(H(n))*log(H(n)), for all n>1, where H(n) is the n-th harmonic number (Jeffrey Lagarias). See A057641 for more details. - Ilya Gutkovskiy, Jul 05 2016
a(n) is the total number of even parts in the partitions of 2*n into equal parts. More generally, a(n) is the total number of parts congruent to 0 mod k in the partitions of k*n into equal parts (the comment dated Jan 16 2013 is the case for k = 1). - Omar E. Pol, Nov 18 2019
a(n) is also the number of order-n subgroups of C_n X C_n, where C_n is the cyclic group of order n. Proof: by the correspondence theorem in the group theory, there is a one-to-one correspondence between the order-n subgroups of C_n X C_n = (Z x Z)/(nZ x nZ) and the index-n subgroups of Z x Z containing nZ x nZ. But an index-n normal subgroup of a (multiplicative) group G contains {g^n : n in G} automaticly. The desired result follows from the comment from Naohiro Nomoto above.
The number of subgroups of C_n X C_n that are isomorphic to C_n is A001615(n). (End)
|
|
|
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. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 116ff.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 162, #16, (6), 2nd formula.
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, AMS Chelsea Publishing, Providence, Rhode Island, 2002, pp. 141, 166.
H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Clarendon Press, Oxford, 2003.
Ross Honsberger, "Mathematical Gems, Number One," The Dolciani Mathematical Expositions, Published and Distributed by The Mathematical Association of America, page 116.
Kanold, Hans Joachim, Kreisteilungspolynome und ungerade vollkommene Zahlen. (German), Ber. Math.-Tagung Tübingen 1946, (1947). pp. 84-87.
M. Krasner, Le nombre des surcorps primitifs d'un degré donné et le nombre des surcorps métagaloisiens d'un degré donné d'un corps de nombres p-adiques. Comptes Rendus Hebdomadaires, Académie des Sciences, Paris 254, 255, 1962.
A. Lubotzky, Counting subgroups of finite index, Proceedings of the St. Andrews/Galway 93 group theory meeting, Th. 2.1. LMS Lecture Notes Series no. 212 Cambridge University Press 1995.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section III.1, page 77.
G. Polya, Induction and Analogy in Mathematics, vol. 1 of Mathematics and Plausible Reasoning, Princeton Univ Press 1954, page 92.
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).
Robert M. Young, Excursions in Calculus, The Mathematical Association of America, 1992 p. 361.
|
|
|
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].
J. W. L. Glaisher, On the function chi(n), Quarterly Journal of Pure and Applied Mathematics, 20 (1884), 97-167.
J. W. L. Glaisher, On the function chi(n), Quarterly Journal of Pure and Applied Mathematics, 20 (1884), 97-167. [Annotated scanned copy]
|
|
|
FORMULA
|
Multiplicative with a(p^e) = (p^(e+1)-1)/(p-1). - David W. Wilson, Aug 01 2001
For the following bounds and many others, see Mitrinovic et al. - N. J. A. Sloane, Oct 02 2017
If n is composite, a(n) > n + sqrt(n).
a(n) < n*sqrt(n) for all n.
a(n) < (6/Pi^2)*n^(3/2) for n > 12.
G.f.: -x*deriv(eta(x))/eta(x) where eta(x) = Product_{n>=1} (1-x^n). - Joerg Arndt, Mar 14 2010
L.g.f.: -log(Product_{j>=1} (1-x^j)) = Sum_{n>=1} a(n)/n*x^n. - Joerg Arndt, Feb 04 2011
Dirichlet convolution of phi(n) and tau(n), i.e., a(n) = sum_{d|n} phi(n/d)*tau(d), cf. A000010, A000005.
a(n) = f(n, 1, 1, 1), where f(n, i, x, s) = if n = 1 then s*x else if p(i)|n then f(n/p(i), i, 1+p(i)*x, s) else f(n, i+1, 1, s*x) with p(i) = i-th prime (A000040). - Reinhard Zumkeller, Nov 17 2004
Recurrence: n^2*(n-1)*a(n) = 12*Sum_{k=1..n-1} (5*k*(n-k) - n^2)*a(k)*a(n-k), if n>1. - Dominique Giard (dominique.giard(AT)gmail.com), Jan 11 2005
G.f.: Sum_{k>0} k * x^k / (1 - x^k) = Sum_{k>0} x^k / (1 - x^k)^2. Dirichlet g.f.: zeta(s)*zeta(s-1). - Michael Somos, Apr 05 2003. See the Hardy-Wright reference, p. 312. first equation, and p. 250, Theorem 290. - Wolfdieter Lang, Dec 09 2016
Equals the inverse Moebius transform of the natural numbers. Equals row sums of A127093. - Gary W. Adamson, May 20 2007
A127093 * [1/1, 1/2, 1/3, ...] = [1/1, 3/2, 4/3, 7/4, 6/5, 12/6, 8/7, ...]. Row sums of triangle A135539. - Gary W. Adamson, Oct 31 2007
G.f.: A(x) = x/(1-x)*(1 - 2*x*(1-x)/(G(0) - 2*x^2 + 2*x)); G(k) = -2*x - 1 - (1+x)*k + (2*k+3)*(x^(k+2)) - x*(k+1)*(k+3)*((-1 + (x^(k+2)))^2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 06 2011
a(n) = Sum{i=1..n} Sum{j=1..i} cos((2*Pi*n*j)/i). - Michel Lagneau, Oct 14 2015
a(n) = (Pi^2*n/6)*Sum_{q>=1} c_q(n)/q^2, with the Ramanujan sums c_q(n) given in A054533 as a c_n(k) table. See the Hardy reference, p. 141, or Hardy-Wright, Theorem 293, p. 251. - Wolfdieter Lang, Jan 06 2017
G.f. also (1 - E_2(q))/24, with the g.f. E_2 of A006352. See e.g., Hardy, p. 166, eq. (10.5.5). - Wolfdieter Lang, Jan 31 2017
a(n) = Sum_{q=1..n} c_q(n) * floor(n/q), where c_q(n) is the Ramanujan's sum function given in A054533. - Daniel Suteu, Jun 14 2018
a(n) = Sum_{k=1..n} gcd(n, k) / phi(n / gcd(n, k)), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 21 2018
G.f.: A(x) = Sum_{n >= 1} x^(n^2)*(x^n + n*(1 - x^(2*n)))/(1 - x^n)^2 - differentiate equation 5 in Arndt w.r.t. x, and set x = 1.
A(x) = F(x) + G(x), where F(x) is the g.f. of A079667 and G(x) is the g.f. of A117004. (End)
a(n) = Sum_{k=1..n} tau(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
With the convention that a(n) = 0 for n <= 0 we have the recurrence a(n) = t(n) + Sum_{k >= 1} (-1)^(k+1)*(2*k + 1)*a(n - k*(k + 1)/2), where t(n) = (-1)^(m+1)*(2*m+1)*n/3 if n = m*(m + 1)/2, with m positive, is a triangular number else t(n) = 0. For example, n = 10 = (4*5)/2 is a triangular number, t(10) = -30, and so a(10) = -30 + 3*a(9) - 5*a(7) + 7*a(4) = -30 + 39 - 40 + 49 = 18. - Peter Bala, Apr 06 2022
Recurrence: a(p^x) = p*a(p^(x-1)) + 1, if p is prime and for any integer x. E.g., a(5^3) = 5*a(5^2) + 1 = 5*31 + 1 = 156. - Jules Beauchamp, Nov 11 2022
|
|
|
EXAMPLE
|
For example, 6 is divisible by 1, 2, 3 and 6, so sigma(6) = 1 + 2 + 3 + 6 = 12.
Let L = <V,W> be a 2-dimensional lattice. The 7 sublattices of index 4 are generated by <4V,W>, <V,4W>, <4V,W+-V>, <2V,2W>, <2V+W,2W>, <2V,2W+V>. Compare A001615.
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
Table[ DivisorSigma[1, n], {n, 100}]
a[ n_] := SeriesCoefficient[ QPolyGamma[ 1, 1, q] / Log[q]^2, {q, 0, n}]; (* Michael Somos, Apr 25 2013 *)
|
|
|
PROG
|
(Magma) [SumOfDivisors(n): n in [1..70]];
(Magma) [DivisorSigma(1, n): n in [1..70]]; // Bruno Berselli, Sep 09 2015
(PARI) {a(n) = if( n<1, 0, sigma(n))};
(PARI) {a(n) = if( n<1, 0, direuler( p=2, n, 1 / (1 - X) /(1 - p*X))[n])};
(PARI) {a(n) = if( n<1, 0, polcoeff( sum( k=1, n, x^k / (1 - x^k)^2, x * O(x^n)), n))}; /* Michael Somos, Jan 29 2005 */
(PARI) max_n = 30; ser = - sum(k=1, max_n, log(1-x^k)); a(n) = polcoeff(ser, n)*n \\ Gottfried Helms, Aug 10 2009
(SageMath) [sigma(n, 1) for n in range(1, 71)] # Zerinvary Lajos, Jun 04 2009
(Haskell)
a000203 n = product $ zipWith (\p e -> (p^(e+1)-1) `div` (p-1)) (a027748_row n) (a124010_row n)
(Scheme) (define (A000203 n) (let ((r (sqrt n))) (let loop ((i (inexact->exact (floor r))) (s (if (integer? r) (- r) 0))) (cond ((zero? i) s) ((zero? (modulo n i)) (loop (- i 1) (+ s i (/ n i)))) (else (loop (- i 1) s)))))) ;; (Stand-alone program) - Antti Karttunen, Feb 20 2024
(GAP)
(Python)
from sympy import divisor_sigma
def a(n): return divisor_sigma(n, 1)
(Python)
from math import prod
from sympy import factorint
def a(n): return prod((p**(e+1)-1)//(p-1) for p, e in factorint(n).items())
(APL, Dyalog dialect) A000203 ← +/{ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð} ⍝ Antti Karttunen, Feb 20 2024
|
|
|
CROSSREFS
|
sigma_i (i=0..25): A000005, A000203, A001157, A001158, A001159, A001160, A013954, A013955, A013956, A013957, A013958, A013959, A013960, A013961, A013962, A013963, A013964, A013965, A013966, A013967, A013968, A013969, A013970, A013971, A013972, A281959.
Cf. A144736, A158951, A158902, A174740, A147843, A001158, A001160, A001065, A002192, A001001, A001615 (primitive sublattices), A039653, A088580, A074400, A083728, A006352, A002659, A083238, A000593, A050449, A050452, A051731, A027748, A124010, A069192, A057641, A001318.
Cf. also A034448 (sum of unitary divisors).
Cf. A007955 (products of divisors).
|
|
|
KEYWORD
|
easy,core,nonn,nice,mult
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000005
|
|
d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.
(Formerly M0246 N0086)
|
|
+10
4766
|
|
|
|
1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9, 2, 8, 2, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
If the canonical factorization of n into prime powers is Product p^e(p) then d(n) = Product (e(p) + 1). More generally, for k > 0, sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1) is the sum of the k-th powers of the divisors of n.
Number of ways to write n as n = x*y, 1 <= x <= n, 1 <= y <= n. For number of unordered solutions to x*y=n, see A038548.
Note that d(n) is not the number of Pythagorean triangles with radius of the inscribed circle equal to n (that is A078644). For number of primitive Pythagorean triangles having inradius n, see A068068(n).
Number of factors in the factorization of the polynomial x^n-1 over the integers. - T. D. Noe, Apr 16 2003
Also equal to the number of partitions p of n such that all the parts have the same cardinality, i.e., max(p)=min(p). - Giovanni Resta, Feb 06 2006
Equals A127093 as an infinite lower triangular matrix * the harmonic series, [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, May 10 2007
For odd n, this is the number of partitions of n into consecutive integers. Proof: For n = 1, clearly true. For n = 2k + 1, k >= 1, map each (necessarily odd) divisor to such a partition as follows: For 1 and n, map k + (k+1) and n, respectively. For any remaining divisor d <= sqrt(n), map (n/d - (d-1)/2) + ... + (n/d - 1) + (n/d) + (n/d + 1) + ... + (n/d + (d-1)/2) {i.e., n/d plus (d-1)/2 pairs each summing to 2n/d}. For any remaining divisor d > sqrt(n), map ((d-1)/2 - (n/d - 1)) + ... + ((d-1)/2 - 1) + (d-1)/2 + (d+1)/2 + ((d+1)/2 + 1) + ... + ((d+1)/2 + (n/d - 1)) {i.e., n/d pairs each summing to d}. As all such partitions must be of one of the above forms, the 1-to-1 correspondence and proof is complete. - Rick L. Shepherd, Apr 20 2008
Number of subgroups of the cyclic group of order n. - Benoit Jubin, Apr 29 2008
Equals row sums of triangle A159934, equivalent to generating a(n) by convolving A000005 prefaced with a 1; (1, 1, 2, 2, 3, 2, ...) with the INVERTi transform of A000005, (A159933): (1, 1,-1, 0, -1, 2, ...). Example: a(6) = 4 = (1, 1, 2, 2, 3, 2) dot (2, -1, 0, -1, 1, 1) = (2, -1, 0, -2, 3, 2) = 4. - Gary W. Adamson, Apr 26 2009
Number of times n appears in an n X n multiplication table. - Dominick Cancilla, Aug 02 2010
The only numbers k such that tau(k) >= k/2 are 1,2,3,4,6,8,12. - Michael De Vlieger, Dec 14 2016
a(n) is also the number of partitions of 2*n into equal parts, minus the number of partitions of 2*n into consecutive parts. - Omar E. Pol, May 03 2017
Let k(n) = log d(n)*log log n/(log 2 * log n), then lim sup k(n) = 1 (Hardy and Wright, Chapter 18, Theorem 317) and k(n) <= k(6983776800) = 1.537939... (the constant A280235) for every n (Nicolas and Robin, 1983).
There exist infinitely many n such that d(n) = d(n+1) (Heath-Brown, 1984). The number of such integers n <= x is at least c*x/(log log x)^3 (Hildebrand, 1987) but at most O(x/sqrt(log log x)) (Erdős, Carl Pomerance and Sárközy, 1987).
(End)
Number of 2D grids of n congruent rectangles with two different side lengths, in a rectangle, modulo rotation (cf. A038548 for squares instead of rectangles). Also number of ways to arrange n identical objects in a rectangle (NOT modulo rotation, cf. A038548 for modulo rotation); cf. A007425 and A140773 for the 3D case. - Manfred Boergens, Jun 08 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. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.
G. Chrystal, Algebra: An elementary text-book for the higher classes of secondary schools and for colleges, 6th ed, Chelsea Publishing Co., New York 1959 Part II, p. 345, Exercise XXI(16). MR0121327 (22 #12066)
G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th ed., Oxford Univ. Press, 2008.
K. Knopp, Theory and Application of Infinite Series, Blackie, London, 1951, p. 451.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Chap. II. (For inequalities, etc.)
S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. Has many references to this sequence. - N. J. A. Sloane, Jun 02 2014
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).
B. Spearman and K. S. Williams, Handbook of Estimates in the Theory of Numbers, Carleton Math. Lecture Note Series No. 14, 1975; see p. 2.1.
E. C. Titchmarsh, The Theory of Functions, Oxford, 1938, p. 160.
T. Tao, Poincaré's Legacies, Part I, Amer. Math. Soc., 2009, see pp. 31ff for upper bounds on d(n).
|
|
|
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, requires Flash plugin].
G. E. Andrews, Some debts I owe, Séminaire Lotharingien de Combinatoire, Paper B42a, Issue 42, 2000; see (7.1).
J. J. Holt and J. W. Jones, Counting Divisors, Discovering Number Theory, Section 1.4.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
Omar E. Pol, Illustration of initial terms: figure 1, figure 2, figure 3, figure 4, figure 5, (2009), figure 6 (a, b, c), (2013)
|
|
|
FORMULA
|
If n is written as 2^z*3^y*5^x*7^w*11^v*... then a(n)=(z+1)*(y+1)*(x+1)*(w+1)*(v+1)*...
a(n) = 2 iff n is prime.
G.f.: Sum_{n >= 1} a(n) x^n = Sum_{k>0} x^k/(1-x^k). This is usually called THE Lambert series (see Knopp, Titchmarsh).
a(n) <= 2 sqrt(n) [see Mitrinovich, p. 39, also A046522].
a(n) = Sum_{k=1..n} f(k, n) where f(k, n) = 1 if k divides n, 0 otherwise (Mobius transform of A000012). Equivalently, f(k, n) = (1/k)*Sum_{l=1..k} z(k, l)^n with z(k, l) the k-th roots of unity. - Ralf Stephan, Dec 25 2002
G.f.: Sum_{k>0} ((-1)^(k+1) * x^(k * (k + 1)/2) / ((1 - x^k) * Product_{i=1..k} (1 - x^i))). - Michael Somos, Apr 27 2003
a(n) = n - Sum_{k=1..n} (ceiling(n/k) - floor(n/k)). - Benoit Cloitre, May 11 2003
G.f.: Sum_{k>0} x^(k^2)*(1+x^k)/(1-x^k). Dirichlet g.f.: zeta(s)^2. - Michael Somos, Apr 05 2003
Sequence = M*V where M = A129372 as an infinite lower triangular matrix and V = ruler sequence A001511 as a vector: [1, 2, 1, 3, 1, 2, 1, 4, ...]. - Gary W. Adamson, Apr 15 2007
Sequence = M*V, where M = A115361 is an infinite lower triangular matrix and V = A001227, the number of odd divisors of n, is a vector: [1, 1, 2, 1, 2, 2, 2, ...]. - Gary W. Adamson, Apr 15 2007
Sum_{n>0} a(n)/(n^n) = Sum_{n>0, m>0} 1/(n*m). - Gerald McGarvey, Dec 15 2007
Logarithmic g.f.: Sum_{n>=1} a(n)/n * x^n = -log( Product_{n>=1} (1-x^n)^(1/n) ). - Joerg Arndt, May 03 2008
For n > 1, a(n) = 2 + Sum_{k=2..n-1} floor((cos(Pi*n/k))^2). And floor((cos(Pi*n/k))^2) = floor(1/4 * e^(-(2*i*Pi*n)/k) + 1/4 * e^((2*i*Pi*n)/k) + 1/2). - Eric Desbiaux, Mar 09 2010, corrected Apr 16 2011
a(n) = 1 + Sum_{k=1..n} (floor(2^n/(2^k-1)) mod 2) for every n. - Fabio Civolani (civox(AT)tiscali.it), Mar 12 2010
(Sum_{d|n} a(d))^2 = Sum_{d|n} a(d)^3 (J. Liouville).
a(n) = sigma_0(n) = 1 + Sum_{m>=2} Sum_{r>=1} (1/m^(r+1))*Sum_{j=1..m-1} Sum_{k=0..m^(r+1)-1} e^(2*k*Pi*i*(n+(m-j)*m^r)/m^(r+1)). - A. Neves, Oct 04 2010
Sum_{n>=1} a(n)*q^n = (log(1-q) + psi_q(1)) / log(q), where psi_q(z) is the q-digamma function. - Vladimir Reshetnikov, Apr 23 2013
G.f.: Sum_{k>=1} Sum_{j>=1} x^(j*k). - Mats Granvik, Jun 15 2013
The formula above is obtained by expanding the Lambert series Sum_{k>=1} x^k/(1-x^k). - Joerg Arndt, Mar 12 2014
G.f.: Sum_{n>=1} Sum_{d|n} ( -log(1 - x^(n/d)) )^d / d!. - Paul D. Hanna, Aug 21 2014
2*Pi*a(n) = Sum_{m=1..n} Integral_{x=0..2*Pi} r^(m-n)( cos((m-n)*x)-r^m cos(n*x) )/( 1+r^(2*m)-2r^m cos(m*x) )dx, 0 < r < 1 a free parameter. This formula is obtained as the sum of the residues of the Lambert series Sum_{k>=1} x^k/(1-x^k). - Seiichi Kirikami, Oct 22 2015
G.f.: 2*x/(1-x) - Sum_{k>0} x^k*(1-2*x^k)/(1-x^k). - Mamuka Jibladze, Aug 29 2018
a(n) = Sum_{k=1..n} 1/phi(n / gcd(n, k)). - Daniel Suteu, Nov 05 2018
a(k*n) = a(n)*(f(k,n)+2)/(f(k,n)+1), where f(k,n) is the exponent of the highest power of k dividing n and k is prime. - Gary Detlefs, Feb 08 2019
a(n) = 2*log(p(n))/log(n), n > 1, where p(n)= the product of the factors of n = A007955(n). - Gary Detlefs, Feb 15 2019
a(n) = (1/n) * Sum_{k=1..n} sigma(gcd(n,k)), where sigma(n) = sum of divisors of n. - Orges Leka, May 09 2019
a(n) = (1/n)*Sum_{k=1..n} phi(gcd(n,k))*sigma(n/gcd(n,k))/phi(n/gcd(n,k)). (End)
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*cos(2*k*n*Pi/j);
a(n) = Sum_{j=1..n} Sum_{k=1..j} (1/j)*e^(2*k*n*Pi*i/j), where i^2=-1. (End)
|
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 2*x^7 + 4*x^8 + 3*x^9 + ...
|
|
|
MAPLE
|
with(numtheory): A000005 := tau; [ seq(tau(n), n=1..100) ];
|
|
|
MATHEMATICA
|
CoefficientList[Series[(Log[1 - q] + QPolyGamma[1, q])/(q Log[q]), {q, 0, 100}], q] (* Vladimir Reshetnikov, Apr 23 2013 *)
a[ n_] := SeriesCoefficient[ (QPolyGamma[ 1, q] + Log[1 - q]) / Log[q], {q, 0, Abs@n}]; (* Michael Somos, Apr 25 2013 *)
a[ n_] := SeriesCoefficient[ q/(1 - q)^2 QHypergeometricPFQ[ {q, q}, {q^2, q^2}, q, q^2], {q, 0, Abs@n}]; (* Michael Somos, Mar 05 2014 *)
a[n_] := SeriesCoefficient[q/(1 - q) QHypergeometricPFQ[{q, q}, {q^2}, q, q], {q, 0, Abs@n}] (* Mats Granvik, Apr 15 2015 *)
With[{M=500}, CoefficientList[Series[(2x)/(1-x)-Sum[x^k (1-2x^k)/(1-x^k), {k, M}], {x, 0, M}], x]] (* Mamuka Jibladze, Aug 31 2018 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n==0, 0, numdiv(n))}; /* Michael Somos, Apr 27 2003 */
(PARI) {a(n) = n=abs(n); if( n<1, 0, direuler( p=2, n, 1 / (1 - X)^2)[n])}; /* Michael Somos, Apr 27 2003 */
(PARI) {a(n)=polcoeff(sum(m=1, n+1, sumdiv(m, d, (-log(1-x^(m/d) +x*O(x^n) ))^d/d!)), n)} \\ Paul D. Hanna, Aug 21 2014
(Magma) [ NumberOfDivisors(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(Haskell)
divisors 1 = [1]
divisors n = (1:filter ((==0) . rem n)
[2..n `div` 2]) ++ [n]
a = length . divisors
(Haskell)
(Python)
from sympy import divisor_count
for n in range(1, 20): print(divisor_count(n), end=', ') # Stefano Spezia, Nov 05 2018
(Julia)
function tau(n)
i = 2; num = 1
while i * i <= n
if rem(n, i) == 0
e = 0
while rem(n, i) == 0
e += 1
n = div(n, i)
end
num *= e + 1
end
i += 1
end
return n > 1 ? num + num : num
end
|
|
|
CROSSREFS
|
Cf. A007427 (Dirichlet Inverse), A001227, A005237, A005238, A006601, A006558, A019273, A039665, A049051, A001826, A001842, A049820, A051731, A066446, A106737, A129510, A115361, A129372, A127093, A143319, A061017, A091202, A091220, A156552, A159933, A159934, A027750, A163280, A183063, A263730, A034296, A237665.
Factorizations into given number of factors: writing n = x*y (A038548, unordered, A000005, ordered), n = x*y*z (A034836, unordered, A007425, ordered), n = w*x*y*z (A007426, ordered).
|
|
|
KEYWORD
|
easy,core,nonn,nice,mult,hear
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000010
|
|
Euler totient function phi(n): count numbers <= n and prime to n.
(Formerly M0299 N0111)
|
|
+10
3957
|
|
|
|
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Number of elements in a reduced residue system modulo n.
Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity. (A primitive n-th root x is such that x^k is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj Beedassy, Mar 31 2005
Also number of complex Dirichlet characters modulo n; Sum_{k=1..n} a(k) is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006
a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006, corrected Sep 27 2006
a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2, a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk, Jan 25 2007
Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug 09 2008
a(n+2) equals the number of palindromic Sturmian words of length n which are "bispecial", prefix or suffix of two Sturmian words of length n + 1. - Fred Lunnon, Sep 05 2010
Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012
If m has k prime factors, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*n))/phi(n)^(k-1). For example, phi(42*n) = phi(2*n)*phi(3*n)*phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012
The order of the multiplicative group of units modulo n. - Michael Somos, Aug 27 2013
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 30 2016
a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).
a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)
For n > 1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - Roger Ford, Oct 11 2017
a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - Felix Flicker, Nov 08 2017
Number of cyclic Latin squares of order n with the first row in ascending order. - Eduard I. Vatutin, Nov 01 2020
a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - Rémy Sigrist, Jan 17 2021
Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):
Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,
Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
More generally,
Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).
In particular, for sequences involving the Möbius transform:
Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.
Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)
Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):
Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),
Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)
a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - Radoslaw Zak, Nov 29 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. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
M. Baake and U. Grimm, Aperiodic Order Vol. 1: A Mathematical Invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013: see Tables 3.1 and 3.2.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, Chapter V.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
Carl Friedrich Gauss, "Disquisitiones Arithmeticae", Yale University Press, 1965; see p. 21.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, pages 261-264, the Coach theorem.
Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1976, Vol. II, problem 71, p. 126.
P. Ribenboim, The New Book of Prime Number Records.
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
|
phi(n) = n*Product_{distinct primes p dividing n} (1 - 1/p).
Sum_{d divides n} phi(d) = n.
phi(n) = Sum_{d divides n} mu(d)*n/d, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
Dirichlet generating function Sum_{n>=1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1 - x^n) = x/(1 - x)^2.
Multiplicative with a(p^e) = (p - 1)*p^(e-1). - David W. Wilson, Aug 01 2001
a(n) = binomial(n+1, 2) - Sum_{i=1..n-1} a(i)*floor(n/i) (see A000217 for inverse). - Jon Perry, Mar 02 2004
It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n) = 1 (taking n to be primes), lim sup n/(phi(n)*log(log(n))) = e^gamma, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320. - Pieter Moree, Sep 10 2004
a(n) = Sum_{i=1..n} |k(n, i)| where k(n, i) is the Kronecker symbol. Also a(n) = n - #{1 <= i <= n : k(n, i) = 0}. - Benoit Cloitre, Aug 06 2004 [Corrected by Jianing Song, Sep 25 2018]
Conjecture: Sum_{i>=2} (-1)^i/(i*phi(i)) exists and is approximately 0.558 (A335319). - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004
a(n) = Sum_{i=1..n} floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n)), where sigma_2 is A001157.
a(n) = Sum_{i=1..n} floor(tau_k(i*n)/tau_k(i)*tau_k(n)), where tau_3 is A007425.
a(n) = Sum_{i=1..n} floor(rad(i*n)/rad(i)*rad(n)), where rad is A007947. (End)
phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - Gary Detlefs, Apr 21 2012
a(n) = lim_{s->1} n*zeta(s)*(Sum_{d divides n} A008683(d)/(e^(1/d))^(s-1)), for n > 1. - Mats Granvik, Jan 26 2017
Conjecture: a(n) = Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 for n > 1. The sum is over a,b,c such that n*c - a*b = 1. - Benedict W. J. Irwin, Apr 03 2017
a(n) = Sum_{j=1..n} gcd(j, n) cos(2*Pi*j/n) = Sum_{j=1..n} gcd(j, n) exp(2*Pi*i*j/n) where i is the imaginary unit. Notice that the Ramanujan's sum c_n(k) := Sum_{j=1..n, gcd(j, n) = 1} exp(2*Pi*i*j*k/n) gives a(n) = Sum_{k|n} k*c_(n/k)(1) = Sum_{k|n} k*mu(n/k). - Michael Somos, May 13 2018
G.f.: x*d/dx(x*d/dx(log(Product_{k>=1} (1 - x^k)^(-mu(k)/k^2)))), where mu(n) = A008683(n). - Mamuka Jibladze, Sep 20 2018
G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, Sep 06 2019
a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - Hugo Pfoertner, Jun 02 2020
Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
a(2n) = a(n) iff n is odd, and, a(2n) > a(n) iff n is even. (End) [Actually, a(2n) = 2*a(n) for even n. - Jianing Song, Sep 18 2022]
For n > 1, Sum_{k=1..n} phi^{(-1)}(n/gcd(n,k))*a(gcd(n,k))/a(n/gcd(n,k)) = 0, where phi^{(-1)} = A023900.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(n/gcd(n,k)))*rad(n/gcd(n,k))*gcd(n,k) = 0.
Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
a(n) = Sum_{d|n, e|n} gcd(d, e)*mobius(n/d)*mobius(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value p^e - p^(e-1) for n = p^e, a prime power). - Peter Bala, Jan 22 2024
Sum_{n >= 1} phi(n)*x^n/(1 + x^n) = x + 3*x^3 + 5*x^5 + 7*x^7 + ... = Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(4*n-2)). For the first equality see Pólya and Szegő, problem 71, p. 126. - Peter Bala, Feb 29 2024
|
|
|
EXAMPLE
|
G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 2*x^6 + 6*x^7 + 4*x^8 + 6*x^9 + 4*x^10 + ...
a(8) = 4 with {1, 3, 5, 7} units modulo 8. a(10) = 4 with {1, 3, 7, 9} units modulo 10. - Michael Somos, Aug 27 2013
The a(5)=4 cyclic Latin squares with the first row in ascending order are:
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3
2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2
3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1
4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0
(End)
|
|
|
MAPLE
|
with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1
with(numtheory): phi := proc(n) local i, t1, t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]), i=1..nops(t1)); end; # version 2
# Alternative without library function:
A000010List := proc(N) local i, j, phi;
phi := Array([seq(i, i = 1 .. N+1)]);
for i from 2 to N + 1 do
if phi[i] = i then
for j from i by i to N + 1 do
phi[j] := phi[j] - iquo(phi[j], i) od
fi od;
return phi end:
|
|
|
MATHEMATICA
|
Array[EulerPhi, 70]
|
|
|
PROG
|
(Axiom) [eulerPhi(n) for n in 1..100]
(Magma) [ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(PARI) {a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */
(Sage)
# euler_phi is a standard function in Sage.
def A000010(n): return euler_phi(n)
def A000010_list(n): return [ euler_phi(i) for i in range(1, n+1)]
(PARI) { for (n=1, 100000, write("b000010.txt", n, " ", eulerphi(n))); } \\ Harry J. Smith, Apr 26 2009
(Haskell) a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014
(Python)
from sympy.ntheory import totient
print([totient(i) for i in range(1, 70)]) # Indranil Ghosh, Mar 17 2017
(Python) # Note also the implementation in A365339.
(Julia) # Computes the first N terms of the sequence.
function A000010List(N)
phi = [i for i in 1:N + 1]
for i in 2:N + 1
if phi[i] == i
for j in i:i:N + 1
phi[j] -= div(phi[j], i)
end end end
return phi end
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,core,nonn,mult,nice,hear
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000079
|
|
Powers of 2: a(n) = 2^n.
(Formerly M1129 N0432)
|
|
+10
3090
|
|
|
|
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
2^0 = 1 is the only odd power of 2.
Number of subsets of an n-set.
There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.
This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]
Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003
a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.
Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.
With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson
Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004
Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]
Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.
The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).
The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005
With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005
The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.
a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006
Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2]} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007
Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008
a(n) is the number of different ways to run up a staircase with n steps, taking steps of sizes 1, 2, 3, ... and r (r <= n), where the order IS important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian, May 21 2008
a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008
2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008
a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008
Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008
This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009
For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009
Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009
a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009
These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009
a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010
The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011
The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012
For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012
This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013
a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013
Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013
More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013
Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013
a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013
Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013
a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014
The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014
The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014
a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014
a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014
a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015
b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015
a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015
a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015
Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016
Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016
Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017
Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017
Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018
The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018
k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019
a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020
a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021
For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile can not be black. - Greg Dresden and Bora Bursalı, Aug 31 2023
|
|
|
REFERENCES
|
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
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).
V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
|
|
|
LINKS
|
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Anicius Manlius Severinus Boethius, De arithmetica, Book 1, section 9.
Eric Weisstein's World of Mathematics, Abundance
Eric Weisstein's World of Mathematics, Erf
Eric Weisstein's World of Mathematics, Hypercube
Eric Weisstein's World of Mathematics, Subset
|
|
|
FORMULA
|
a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n-1).
G.f.: 1/(1 - 2*x).
E.g.f.: exp(2*x).
a(n)= Sum_{k = 0..n} binomial(n, k).
a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + Sum_{k = 0..(n - 1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004
a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005
a(n) = StirlingS2(n + 1, 2) + 1. - Ross La Haye, Jan 09 2008
a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Aug 06 2008
a(n) = ka(n-1) + (4 - 2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
If p[i] = i - 1 and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 1, a(n-1) = det A. - Milan Janjic, May 02 2010
If p[i] = Fibonacci(i-2) and if A is the Hessenberg matrix of order n defined by: A[i, j] = p[j - i + 1], (i <= j), A[i, j] = -1, (i = j + 1), and A[i, j] = 0 otherwise. Then, for n >= 2, a(n-2) = det A. - Milan Janjic, May 08 2010
The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - Mohammad K. Azarian, Dec 29 2010
a(n) = Hypergeometric([-n], [], -1). - Peter Luschny, Nov 01 2011
G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - Vladimir Kruchinin, Nov 10 2011
2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012
E.g.f.: 1 + 2*x/(U(0) - x) where U(k) = 6*k + 1 + x^2/(6*k+3 + x^2/(6*k + 5 + x^2/U(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012
a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013
a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind (A129467). - Mircea Merca, Apr 06 2013
G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013
a(n-1) = Sum_{t_1 + 2*t_2 + ... + n*t_n = n} multinomial(t_1 + t_2 + ... + t_n; t_1, t_2, ..., t_n). - Mircea Merca, Dec 06 2013
Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015
Exponential convolution of A000012 with themselves.
Sum_{n>=0} a(n)/n! = exp(2) = A072334.
Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End)
G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - Gary W. Adamson, Sep 13 2016
a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - Michael A. Allen, Jan 12 2022
Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - Stefano Spezia, May 17 2023
|
|
|
EXAMPLE
|
There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.
|
|
|
MAPLE
|
A000079 := n->2^n; [ seq(2^n, n=0..50) ];
isA000079 := proc(n)
local fs;
fs := numtheory[factorset](n) ;
if n = 1 then
true ;
elif nops(fs) <> 1 then
false;
elif op(1, fs) = 2 then
true;
else
false ;
end if;
|
|
|
MATHEMATICA
|
Table[2^n, {n, 0, 50}]
CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
|
|
|
PROG
|
(PARI) unimodal(n)=local(x, d, um, umc); umc=0; for (c=0, n!-1, x=numtoperm(n, c); d=0; um=1; for (j=2, n, if (x[j]<x[j-1], d=1); if (x[j]>x[j-1] && d==1, um=0); if (um==0, break)); if (um==1, print(x)); umc+=um); umc
(PARI) x=1; for (n=0, 1000, write("b000079.txt", n, " ", x); x+=x); \\ Harry J. Smith, Apr 26 2009
(Haskell)
a000079 = (2 ^)
a000079_list = iterate (* 2) 1
(Magma) [2^n: n in [0..40]] (* or *) [n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014
(Scala) (List.fill(20)(2: BigInt)).scanLeft(1: BigInt)(_ * _) // Alonso del Arte, Jan 16 2020
(Python)
def a(n): return 1<<n
|
|
|
CROSSREFS
|
Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021.
The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).
|
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Edited by _Daniel Forgues_, May 12 2010
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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
The partial sums give the natural numbers (A000027). - _Daniel Forgues_, May 08 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
|
| |
|
|
| |
|
|
A001221
|
|
Number of distinct primes dividing n (also called omega(n)).
(Formerly M0056 N0019)
|
|
+10
2167
|
|
|
|
0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 3, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 3, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
From Peter C. Heinig (algorithms(AT)gmx.de), Mar 08 2008: (Start)
This is also the number of maximal ideals of the ring (Z/nZ,+,*). Since every finite integral domain must be a field, every prime ideal of Z/nZ is a maximal ideal and since in general each maximal ideal is prime, there are just as many prime ideals as maximal ones in Z/nZ, so the sequence gives the number of prime ideals of Z/nZ as well.
The reason why this number is given by the sequence is that the ideals of Z/nZ are precisely the subgroups of (Z/nZ,+). Hence for an ideal to be maximal it has form a maximal subgroup of (Z/nZ,+) and this is equivalent to having prime index in (Z/nZ) and this is equivalent to being generated by a single prime divisor of n.
Finally, all the groups arising in this way have different orders, hence are different, so the number of maximal ideals equals the number of distinct primes dividing n. (End)
Up to 2*3*5*7*11*13*17*19*23*29 - 1 = 6469693230 - 1, also the decimal expansion of the constant 0.01111211... = Sum_{k>=0} 1/(10 ^ A000040(k) - 1) (see A073668). - Eric Desbiaux, Jan 20 2014
The average order of a(n): Sum_{k=1..n} a(k) ~ Sum_{k=1..n} log log k. - _Daniel Forgues_, Aug 13-16 2015
We can use A001221 and A001222 to classify the positive integers as follows.
Restricting to n > 1:
|
|
|
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. 844.
J. Peters, A. Lodge and E. J. Ternouth, E. Gifford, Factor Table (n<100000) (British Association Mathematical Tables Vol.V), Burlington House/Cambridge University Press London 1935.
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
|
Additive with a(p^e) = 1.
a(1) = 0, a(p) = 1, a(pq) = 2, a(pq...z) = k, a(p^k) = 1, where p, q, ..., z are k distinct primes and k natural numbers. - Jaroslav Krizek, May 04 2009
L.g.f.: -log(Product_{k>=1} (1 - x^prime(k))^(1/prime(k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Jul 30 2018
a(n) = log_2(Sum_{k=1..n} mu(gcd(n,k))^2/phi(n/gcd(n,k))) = log_2(Sum_{k=1..n} mu(n/gcd(n,k))^2/phi(n/gcd(n,k))), where phi = A000010 and mu = A008683. - Richard L. Ollerton, May 13 2021
|
|
|
MAPLE
|
A001221 := proc(n) local t1, i; if n = 1 then return 0 else t1 := 0; for i to n do if n mod ithprime(i) = 0 then t1 := t1 + 1 end if end do end if; t1 end proc;
|
|
|
MATHEMATICA
|
Array[ Length[ FactorInteger[ # ] ]&, 100 ]
|
|
|
PROG
|
(MuPAD) func(nops(numlib::primedivisors(n)), n):
(PARI) a(n)=omega(n)
(Sage)
def A001221(n): return sum(1 for p in divisors(n) if is_prime(p))
(Haskell)
import Math.NumberTheory.Primes.Factorisation (factorise)
a001221 = length . snd . unzip . factorise
(Python)
from sympy.ntheory import primefactors
print([len(primefactors(n)) for n in range(1, 1001)]) # Indranil Ghosh, Mar 19 2017
(Magma) [#PrimeDivisors(n): n in [1..120]]; // Bruno Berselli, Oct 15 2021
(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) for n in 1:60]) # Peter Luschny, Jan 02 2024
|
|
|
CROSSREFS
|
Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.
Sum of the k-th powers of the primes dividing n for k=0..10: this sequence (k=0), A008472 (k=1), A005063 (k=2), A005064 (k=3), A005065 (k=4), A351193 (k=5), A351194 (k=6), A351195 (k=7), A351196 (k=8), A351197 (k=9), A351198 (k=10).
Sequences of the form n^k * Sum_{p|n, p prime} 1/p^k for k=0..10: this sequence (k=0), A069359 (k=1), A322078 (k=2), A351242 (k=3), A351244 (k=4), A351245 (k=5), A351246 (k=6), A351247 (k=7), A351248 (k=8), A351249 (k=9), A351262 (k=10).
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A007318
|
|
Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.
(Formerly M0082)
|
|
+10
2060
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
A. W. F. Edwards writes: "It [the triangle] was first written down long before 1654, the year in which Blaise Pascal wrote his Traité du triangle arithmétique, but it was this work that brought together all the different aspects of the numbers for the first time. In it Pascal developed the properties of the number as a piece of pure mathematics ... and then, in a series of appendices, showed how these properties were relevant to the study of the figurate numbers, to the theory of combinations, to the expansion of binomial expressions, and to the solution of an important problem in the theory of probability." (A. W. F. Edwards, Pascal's Arithmetical Triangle, Johns Hopkins University Press (2002), p. xiii)
Edwards reports that the naming of the triangle after Pascal was done first by Montmort in 1708 as the "Table de M. Pascal pour les combinaisons" and then by De Moivre in 1730 as the "Triangulum Arithmeticum PASCALANIUM". (Edwards, p. xiv)
In China, Yang Hui in 1261 listed the coefficients of (a+b)^n up to n=6, crediting the expansion to Chia Hsein's Shih-so suan-shu circa 1100. Another prominent early use was in Chu Shih-Chieh's Precious Mirror of the Four Elements in 1303. (Edwards, p. 51)
In Persia, Al-Karaji discovered the binomial triangle "some time soon after 1007", and Al-Samawal published it in the Al-bahir some time before 1180. (Edwards, p. 52)
In India, Halayuda's commentary (circa 900) on Pingala's treatise on syllabic combinations (circa 200 B.C.E.) contains a clear description of the additive computation of the triangle. (Amulya Kumar Bag, Binomial Theorem in Ancient India, p. 72)
Also in India, the multiplicative formula for C(n,k) was known to Mahavira in 850 and restated by Bhaskara in 1150. (Edwards, p. 27)
In Italy, Tartaglia published the triangle in his General trattato (1556), and Cardano published it in his Opus novum (1570). (Edwards, p. 39, 44) - Russ Cox, Mar 29 2022
Also sometimes called Omar Khayyam's triangle.
Also sometimes called Yang Hui's triangle.
C(n,k) = number of k-element subsets of an n-element set.
Row n gives coefficients in expansion of (1+x)^n.
Binomial(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).
Binomial(n-1,k-1) is the number of compositions (ordered partitions) of n with k summands.
Binomial(n+k-1,k-1) is the number of weak compositions (ordered weak partitions) of n into exactly k summands. - Juergen Will, Jan 23 2016
Binomial(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). - Joerg Arndt, Jul 01 2011
If thought of as an infinite lower triangular matrix, inverse begins:
+1
-1 +1
+1 -2 +1
-1 +3 -3 +1
+1 -4 +6 -4 +1
All 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are odd. - Lekraj Beedassy, May 20 2003
Binomial(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch, May 13 2004
Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinant of each of its n X n subarrays starting at (0,0) is 1. - Gerald McGarvey, Aug 17 2004
Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006
Binomial(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. Binomial(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007
Consider integer lists LL of lists L of the form LL = [m#L] = [m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to binomial(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are counted only once. For the example, we find 4*5*6/3! = 20 = binomial(6,3). - Thomas Wieder, Oct 03 2007
The infinitesimal generator for Pascal's triangle and its inverse is A132440. - Tom Copeland, Nov 15 2007
Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g., row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd, Nov 25 2007
From Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: (Start)
Binomial(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).
Binomial(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are binomial(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also binomial(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). (End)
Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then:
Binomial(2n+1,2k+1) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2(i*Pi/(2n+1)), (i=1,2,...,n).
Binomial(2n,2k+1) = 2n*sigma_{n-1-k}(x_1,x_2,...,x_{n-1}), where x_i = tan^2(i*Pi/(2n)), (i=1,2,...,n-1).
Binomial(2n,2k) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n)), (i=1,2,...,n).
Binomial(2n+1,2k) = (2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). (End)
Given matrices R and S with R(n,k) = binomial(n,k)*r(n-k) and S(n,k) = binomial(n,k)*s(n-k), then R*S = T where T(n,k) = binomial(n,k)*[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(x*t)*exp[r(.)*x], exp(x*t)*exp[s(.)*x] and exp(x*t)*exp[r(.)*x]*exp[s(.)*x] = exp{[t+r(.)+s(.)]*x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. - Tom Copeland, Aug 21 2008
As the rectangle R(m,n) = binomial(m+n-2,m-1), the weight array W (defined generally at A144112) of R is essentially R itself, in the sense that if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. - Clark Kimberling, Sep 15 2008
If A007318 = M as an infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 11 2008
The coefficients of the polynomials with e.g.f. exp(x*t)*(cosh(t)+sinh(t)). - Peter Luschny, Jul 09 2009
The triangle or chess sums, see A180662 for their definitions, link Pascal's triangle with twenty different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 - Kn110 have been added. It is remarkable that all knight sums are related to the Fibonacci numbers, i.e., A000045, but none of the others. - Johannes W. Meijer, Sep 22 2010
Binomial(n,k) is also the number of ways to distribute n+1 balls into k+1 urns so that each urn gets at least one ball. See example in the example section below. - Dennis P. Walsh, Jan 29 2011
Binomial(n,k) is the number of increasing functions from {1,...,k} to {1,...,n} since there are binomial(n,k) ways to choose the k distinct, ordered elements of the range from the codomain {1,...,n}. See example in the example section below. - Dennis P. Walsh, Apr 07 2011
Binomial(n,k) is the number of subsets of {1,...,n+1} with k+1 as median element. To see this, note that Sum_{j=0..min(k,n-k)}binomial(k,j)*binomial(n-k,j) = binomial(n,k). See example in Example section below. - Dennis P. Walsh, Dec 15 2011
This is the coordinator triangle for the lattice Z^n, see Conway-Sloane, 1997. - N. J. A. Sloane, Jan 17 2012
One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A046521 and A068555. For real r >= 0, C_r(n,k) := floor(r*n)!/(floor(r*k)!*floor(r*(n-k))!) is integral. See A211226 for the case r = 1/2. - Peter Bala, Apr 10 2012
Define a finite triangle T(m,k) with n rows such that T(m,0) = 1 is the left column, T(m,m) = binomial(n-1,m) is the right column, and the other entries are T(m,k) = T(m-1,k-1) + T(m-1,k) as in Pascal's triangle. The sum of all entries in T (there are A000217(n) elements) is 3^(n-1). - J. M. Bergot, Oct 01 2012
The lower triangular Pascal matrix serves as a representation of the operator exp(RLR) in a basis composed of a sequence of polynomials p_n(x) characterized by ladder operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x). See A132440, A218272, A218234, A097805, and A038207. The transposed and padded Pascal matrices can be associated to the special linear group SL2. - Tom Copeland, Oct 25 2012
A permutation p_1...p_n of the set {1,...,n} has a descent at position i if p_i > p_(i+1). Let S(n) denote the subset of permutations p_1...p_n of {1,...,n} such that p_(i+1) - p_i <= 1 for i = 1,...,n-1. Then binomial(n,k) gives the number of permutations in S(n+1) with k descents. Alternatively, binomial(n,k) gives the number of permutations in S(n+1) with k+1 increasing runs. - Peter Bala, Mar 24 2013
Sum_{n=>0} binomial(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where binomial(n,k) = 0. Also Sum_{n>=0} binomial(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
The square n X n submatrix (first n rows and n columns) of the Pascal matrix P(x) defined in the formulas below when multiplying on the left the Vandermonde matrix V(x_1,...,x_n) (with ones in the first row) translates the matrix to V(x_1+x,...,x_n+x) while leaving the determinant invariant. - Tom Copeland, May 19 2014
For k>=2, n>=k, k/((k/(k-1) - Sum_{n=k..m} 1/binomial(n,k))) = m!/((m-k+1)!*(k-2)!). Note: k/(k-1) is the infinite sum. See A000217, A000292, A000332 for examples. - Richard R. Forberg, Aug 12 2014
Let G_(2n) be the subgroup of the symmetric group S_(2n) defined by G_(2n) = {p in S_(2n) | p(i) = i (mod n) for i = 1,2,...,2n}. G_(2n) has order 2^n. Binomial(n,k) gives the number of permutations in G_(2n) having n + k cycles. Cf. A130534 and A246117. - Peter Bala, Aug 15 2014
C(n,k) = the number of Dyck paths of semilength n+1, with k+1 "u"'s in odd numbered positions and k+1 returns to the x axis. Example: {U = u in odd position and _ = return to x axis} binomial(3,0)=1 (Uudududd_); binomial(3,1)=3 [(Uududd_Ud_), (Ud_Uududd_), (Uudd_Uudd_)]; binomial(3,2)=3 [(Ud_Ud_Uudd_), (Uudd_Ud_Ud_), (Ud_Uudd_Ud_)]; binomial(3,3)=1 (Ud_Ud_Ud_Ud_). - Roger Ford, Nov 05 2014
From _Daniel Forgues_, Mar 12 2015: (Start)
The binomial coefficients binomial(n,k) give the number of individuals of the k-th generation after n population doublings. For each doubling of population, each individual's clone has its generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to 2^n - 1 to get the binomial coefficients.
0 1 3 7 15
0: O | . | . . | . . . . | . . . . . . . . |
1: | O | O . | O . . . | O . . . . . . . |
2: | | O | O O . | O O . O . . . |
3: | | | O | O O O . |
4: | | | | O |
This is a fractal process: to get the pattern from 0 to 2^n - 1, append a shifted down (by one row) copy of the pattern from 0 to 2^(n-1) - 1 to the right of the pattern from 0 to 2^(n-1) - 1. (Inspired by the "binomial heap" data structure.)
Sequence of generation indices: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n) (see A000120):
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...}
Binary expansion of 0 to 15:
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1111
(End)
T(n,k) is the number of set partitions w of [n+1] that avoid 1/2/3 with rb(w)=k. The same holds for ls(w)=k, where avoidance is in the sense of Klazar and ls,rb defined by Wachs and White.
Let {A(n)} be a set with exactly n identical elements, with {A(0)} being the empty set E. Let {A(n,k)} be the k-th iteration of {A(n)}, with {A(n,0)} = {A(n)}. {A(n,1)} = The set of all the subsets of A{(n)}, including {A(n)} and E. {A(n,k)} = The set of all subsets of {A(n,k-1)}, including all of the elements of {A(n,k-1)}. Let A(n,k) be the number of elements in {A(n,k)}. Then A(n,k) = C(n+k,k), with each successive iteration replicating the members of the k-th diagonal of Pascal's Triangle. See examples. - Gregory L. Simay, Aug 06 2018
Binomial(n-1,k) is also the number of permutations avoiding both 213 and 312 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n-1,k) is also the number of permutations avoiding both 132 and 213 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n,k) is the dimension of the k-th exterior power of a vector space of dimension n. - Stefano Spezia, Dec 22 2018
C(n,k-1) is the number of unoriented colorings of the facets (or vertices) of an n-dimensional simplex using exactly k colors. Each chiral pair is counted as one when enumerating unoriented arrangements. - Robert A. Russell, Oct 20 2020
From Dilcher and Stolarsky: "Two of the most ubiquitous objects in mathematics are the sequence of prime numbers and the binomial coefficients (and thus Pascal's triangle). A connection between the two is given by a well-known characterization of the prime numbers: Consider the entries in the kth row of Pascal's triangle, without the initial and final entries. They are all divisible by k if and only if k is a prime." - Tom Copeland, May 17 2021
Named "Table de M. Pascal pour les combinaisons" by Pierre Remond de Montmort (1708) after the French mathematician, physicist and philosopher Blaise Pascal (1623-1662). - Amiram Eldar, Jun 11 2021
Consider the n-th diagonal of the triangle as a sequence b(n) with n starting at 0. From it form a new sequence by leaving the 0th term as is, and thereafter considering all compositions of n, taking the product of b(i) over the respective numbers i in each composition, adding terms corresponding to compositions with an even number of parts subtracting terms corresponding to compositions with an odd number of parts. Then the n-th row of the triangle is obtained, with every second term multiplied by -1, followed by infinitely many zeros. For sequences starting with 1, this operation is a special case of a self-inverse operation, and therefore the converse is true. - Thomas Anton, Jul 05 2021
C(n,k) is the number of vertices in an n-dimensional unit hypercube, at an L1 distance of k (or: with a shortest path of k 1d-edges) from a given vertex. - Eitan Y. Levine, May 01 2023
C(n+k-1,k-1) is the number of vertices at an L1 distance from a given vertex in an infinite-dimensional box, which has k sides of length 2^m for each m >= 0. Equivalently, given a set of tokens containing k distinguishable tokens with value 2^m for each m >= 0, C(n+k-1,k-1) is the number of subsets of tokens with a total value of n. - Eitan Y. Levine, Jun 11 2023
Numbers in the k-th column, i.e., numbers of the form C(n,k) for n >= k, are known as k-simplex numbers. - Pontus von Brömssen, Jun 26 2023
Let r(k) be the k-th row and c(k) the k-th column. Denote convolution by * and repeated convolution by ^. Then r(k)*r(m)=r(k+m) and c(k)*c(m)=c(k+m+1). This is because r(k) = r(1) ^ k and c(k) = c(0) ^ k+1. - Eitan Y. Levine, Jul 23 2023
Number of permutations of length n avoiding simultaneously the patterns 231 and 312(resp., 213 and 231; 213 and 312) with k descents (equivalently, with k ascents). An ascent (resp., descent) in a permutation a(1)a(2)...a(n) is position i such that a(i)<a(i+1) (resp., a(i)>a(i+1)). - Tian Han, Nov 25 2023
C(n,k) are generalized binomial coefficients of order m=0. Calculated by the formula С(n,k) = Sum_{i=0..n-k} binomial(n+1, n-k-i)*Stirling2(i+ m+ 1, i+1) *(-1)^i, where m = 0 for n>= 0, 0 <= k <= n. - Igor Victorovich Statsenko, Feb 26 2023
|
|
|
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. 828.
Amulya Kumar Bag, Binomial theorem in ancient India, Indian Journal of History of Science, vol. 1 (1966), pp. 68-74.
Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.
P. Curtz, Intégration numérique des systèmes différentiels à conditions initiales, Centre de Calcul Scientifique de l'Armement, Arcueil, 1969.
A. W. F. Edwards, Pascal's Arithmetical Triangle, 2002.
William Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.
David Hök, Parvisa mönster i permutationer [Swedish], 2007.
Donald E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.
Sergei K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.
Blaise Pascal, Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière, Desprez, Paris, 1665.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
A. P. Prudnikov, Yu. A. Brychkov and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.
John Riordan, Combinatorial Identities, Wiley, 1968, p. 2.
Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 115-118.
Douglas B. West, Combinatorial Mathematics, Cambridge, 2021, p. 25.
|
|
|
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].
A. Farina, S. Giompapa, A. Graziano, A. Liburdi, M. Ravanelli and F. Zirilli, Tartaglia-Pascal's triangle: a historical perspective with applications, Signal, Image and Video Processing, Vol. 7, No. 1 (January 2013), pp. 173-188.
Subhash Kak, The golden mean and the physics of aesthetics, in: B. Yadav and M. Mohan (eds.), Ancient Indian Leaps into Mathematics, Birkhäuser, Boston, MA, 2009, pp. 111-119; arXiv preprint, arXiv:physics/0411195 [physics.hist-ph], 2004.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
Jack Ramsay, On Arithmetical Triangles, The Pulse of Long Island, June 1965 [Mentions application to design of antenna arrays. Annotated scan.]
Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan and Leon C. Woodson, The Riordan group, Discrete Applied Math., Vol. 34 (1991), pp. 229-239.
Christopher Stover and Eric W. Weisstein, Composition. From MathWorld - A Wolfram Web Resource.
|
|
|
FORMULA
|
a(n, k) = C(n,k) = binomial(n, k).
C(n, k) = C(n-1, k) + C(n-1, k-1).
The triangle is symmetric: C(n,k) = C(n,n-k).
a(n+1, m) = a(n, m) + a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n<m; a(0, 0)=1.
C(n, k) = n!/(k!(n-k)!) if 0<=k<=n, otherwise 0.
G.f.: 1/(1-y-x*y) = Sum_(C(n, k)*x^k*y^n, n, k>=0)
G.f.: 1/(1-x-y) = Sum_(C(n+k, k)*x^k*y^n, n, k>=0).
G.f. for row n: (1+x)^n = Sum_{k=0..n} C(n, k)*x^k.
G.f. for column k: x^k/(1-x)^(k+1); [corrected by Werner Schulte, Jun 15 2022].
E.g.f.: A(x, y) = exp(x+x*y).
E.g.f. for column n: x^n*exp(x)/n!.
In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k)*C(n, k).
Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
Let P(n+1) = the number of integer partitions of (n+1); let p(i) = the number of parts of the i-th partition of (n+1); let d(i) = the number of different parts of the i-th partition of (n+1); let m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1). Define the operator Sum_{i=1..P(n+1), p(i)=k+1} as the sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account. Define the operator Product_{j=1..d(i)} = product running from j=1 to j=d(i). Then C(n, k) = Sum_{p(i)=(k+1), i=1..P(n+1)} p(i)! / [Product_{j=1..d(i)} m(i, j)!]. E.g., C(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!*1!) = 3; (123): 3!/(1!*1!*1!) = 6; (222): 3!/3! = 1. The sum is 3 + 6 + 1 = 10 = C(5, 3). - Thomas Wieder, Jun 03 2005
G.f.: 1 + x*(1 + x) + x^3*(1 + x)^2 + x^6*(1 + x)^3 + ... . - Michael Somos, Sep 16 2006
Sum_{k=0..floor(n/2)} x^(n-k)*T(n-k,k) = A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. Sum_{k=0..floor(n/2)} (-1)^k*x^(n-k)*T(n-k,k) = A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, respectively. - Philippe Deléham, Sep 16 2006
C(t+p-1, t) = Sum_{i=0..t} C(i+p-2, i) = Sum_{i=1..p} C(i+t-2, t-1). A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008
Let A(x) = Sum_{n>=0} x^(n*(n+1)/2)*(1+x)^n be the g.f. of the flattened triangle:
A(x) = 1 + (x + x^2) + (x^3 + 2*x^4 + x^5) + (x^6 + 3*x^7 + 3*x^8 + x^9) + ...
then A(x) equals the series Sum_{n>=0} (1+x)^n*x^n*Product_{k=1..n} (1-(1+x)*x^(2*k-1))/(1-(1+x)*x^(2*k));
also, A(x) equals the continued fraction 1/(1- x*(1+x)/(1+ x*(1-x)*(1+x)/(1- x^3*(1+x)/(1+ x^2*(1-x^2)*(1+x)/(1- x^5*(1+x)/(1+ x^3*(1-x^3)*(1+x)/(1- x^7*(1+x)/(1+ x^4*(1-x^4)*(1+x)/(1- ...))))))))).
These formulas are due to (1) a q-series identity and (2) a partial elliptic theta function expression. (End)
Row n of the triangle is the result of applying the ConvOffs transform to the first n terms of the natural numbers (1, 2, 3, ..., n). See A001263 or A214281 for a definition of this transformation. - Gary W. Adamson, Jul 12 2012
Row n (n >= 0) of the triangle is given by the n-th antidiagonal of the infinite matrix P^n, where P = (p_{i,j}), i,j >= 0, is the production matrix
0, 1,
1, 0, 1,
0, 1, 0, 1,
0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0, 1,
... (End)
Row n of the triangle is also given by the n+1 coefficients of the polynomial P_n(x) defined by the recurrence P_0(x) = 1, P_1(x) = x + 1, P_n(x) = x*P_{n-1}(x) + P_{n-2}(x), n > 1. - L. Edson Jeffery, Aug 12 2013
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 18 2013
(1+x)^n = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{i=0..k} k^(n-i)*binomial(k,i)*x^(n-i)/(n-i)!. - Vladimir Kruchinin, Oct 21 2013
E.g.f.: A(x,y) = exp(x+x*y) = 1 + (x+y*x)/( E(0)-(x+y*x)), where E(k) = 1 + (x+y*x)/(1 + (k+1)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
E.g.f.: E(0) -1, where E(k) = 2 + x*(1+y)/(2*k+1 - x*(1+y)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
G.f.: 1 + x*(1+x)*(1+x^2*(1+x)/(W(0)-x^2-x^3)), where W(k) = 1 + (1+x)*x^(k+2) - (1+x)*x^(k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
Sum_{n>=0} C(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where C(n,k) = 0. Also Sum_{n>=0} C(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result by A007318(x) = P(x). Then with :xD:^n = x^n*(d/dx)^n and B(n,x), the Bell polynomials (A008277),
A) P(x)= exp(x*dP) = exp[x*(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x)
B) P(:xD:) = exp(dP:xD:) = exp[(e^M-I):xD:] = exp[M*B(.,:xD:)] = exp[M*xD] = (I+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x] (cf. also A238363).
C) P(x)^y = P(y*x). P(2x) = A038207(x) = exp[M*B(.,2x)], the face vectors of the n-dim hypercubes.
D) P(x) = [St2]*exp(x*M)*[St1] = [St2]*(I+dP)^x*[St1]
E) = [St1]^(-1)*(I+dP)^x*[St1] = [St2]*(I+dP)^x*[St2]^(-1)
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and exp(x*M) = (I+dP)^x = Sum_{k>=0} C(x,k) dP^k. (End)
Recurrence equation: T(n,k) = T(n-1,k)*(n + k)/(n - k) - T(n-1,k-1) for n >= 2 and 1 <= k < n, with boundary conditions T(n,0) = T(n,n) = 1. Note, changing the minus sign in the recurrence to a plus sign gives a recurrence for the square of the binomial coefficients - see A008459.
There is a relation between the e.g.f.'s of the rows and the diagonals of the triangle, namely, exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(1 + 3*x + 3*x^2/2! + x^3/3!) = 1 + 4*x + 10*x^2/2! + 20*x^3/3! + 35*x^4/4! + .... This property holds more generally for the Riordan arrays of the form ( f(x), x/(1 - x) ), where f(x) is an o.g.f. of the form 1 + f_1*x + f_2*x^2 + .... See, for example, A055248 and A106516.
Let P denote the present triangle. For k = 0,1,2,... define P(k) to be the lower unit triangular block array
/I_k 0\
\ 0 P/ having the k X k identity matrix I_k as the upper left block; in particular, P(0) = P. The infinite product P(0)*P(1)*P(2)*..., which is clearly well-defined, is equal to the triangle of Stirling numbers of the second kind A008277. The infinite product in the reverse order, that is, ...*P(2)*P(1)*P(0), is equal to the triangle of Stirling cycle numbers A130534. (End)
C(a+b,c) = Sum_{k=0..a} C(a,k)*C(b,b-c+k). This is a generalization of equation 1 from section 4.2.5 of the Prudnikov et al. reference, for a=b=c=n: C(2*n,n) = Sum_{k=0..n} C(n,k)^2. See Links section for animation of new formula. - Hermann Stamm-Wilbrandt, Aug 26 2015
The row polynomials of the Pascal matrix P(n,x) = (1+x)^n are related to the Bernoulli polynomials Br(n,x) and their umbral compositional inverses Bv(n,x) by the umbral relation P(n,x) = (-Br(.,-Bv(.,x)))^n = (-1)^n Br(n,-Bv(.,x)), which translates into the matrix relation P = M * Br * M * Bv, where P is the Pascal matrix, M is the diagonal matrix diag(1,-1,1,-1,...), Br is the matrix for the coefficients of the Bernoulli polynomials, and Bv that for the umbral inverse polynomials defined umbrally by Br(n,Bv(.,x)) = x^n = Bv(n,Br(.,x)). Note M = M^(-1). - Tom Copeland, Sep 05 2015
1/(1-x)^k = (r(x) * r(x^2) * r(x^4) * ...) where r(x) = (1+x)^k. - Gary W. Adamson, Oct 17 2016
Boas-Buck type recurrence for column k for Riordan arrays (see the Aug 10 2017 remark in A046521, also for the reference) with the Boas-Buck sequence b(n) = {repeat(1)}. T(n, k) = ((k+1)/(n-k))*Sum_{j=k..n-1} T(j, k), for n >= 1, with T(n, n) = 1. This reduces, with T(n, k) = binomial(n, k), to a known binomial identity (e.g, Graham et al. p. 161). - Wolfdieter Lang, Nov 12 2018
C((p-1)/a, b) == (-1)^b * fact_a(a*b-a+1)/fact_a(a*b) (mod p), where fact_n denotes the n-th multifactorial, a divides p-1, and the denominator of the fraction on the right side of the equation represents the modular inverse. - Isaac Saffold, Jan 07 2019
Binomial sums are Fibonacci numbers A000045:
Sum_{k=0..n} C(n + k, 2*k + 1) = F(2*n).
Sum_{k=0..n} C(n + k, 2*k) = F(2*n + 1). (End)
|
|
|
EXAMPLE
|
Triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 ...
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1
...
There are C(4,2)=6 ways to distribute 5 balls BBBBB, among 3 different urns, < > ( ) [ ], so that each urn gets at least one ball, namely, <BBB>(B)[B], <B>(BBB)[B], <B>(B)[BBB], <BB>(BB)[B], <BB>(B)[BB], and <B>(BB)[BB].
There are C(4,2)=6 increasing functions from {1,2} to {1,2,3,4}, namely, {(1,1),(2,2)},{(1,1),(2,3)}, {(1,1),(2,4)}, {(1,2),(2,3)}, {(1,2),(2,4)}, and {(1,3),(2,4)}. - Dennis P. Walsh, Apr 07 2011
There are C(4,2)=6 subsets of {1,2,3,4,5} with median element 3, namely, {3}, {1,3,4}, {1,3,5}, {2,3,4}, {2,3,5}, and {1,2,3,4,5}. - Dennis P. Walsh, Dec 15 2011
The successive k-iterations of {A(0)} = E are E;E;E;...; the corresponding number of elements are 1,1,1,... The successive k-iterations of {A(1)} = {a} are (omitting brackets) a;a,E; a,E,E;...; the corresponding number of elements are 1,2,3,... The successive k-iterations of {A(2)} = {a,a} are aa; aa,a,E; aa, a, E and a,E and E;...; the corresponding number of elements are 1,3,6,... - Gregory L. Simay, Aug 06 2018
Boas-Buck type recurrence for column k = 4: T(8, 4) = (5/4)*(1 + 5 + 15 + 35) = 70. See the Boas-Buck comment above. - Wolfdieter Lang, Nov 12 2018
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
Flatten[Table[Binomial[n, k], {n, 0, 11}, {k, 0, n}]] (* Robert G. Wilson v, Jan 19 2004 *)
Flatten[CoefficientList[CoefficientList[Series[1/(1 - x - x*y), {x, 0, 12}], x], y]] (* Mats Granvik, Jul 08 2014 *)
|
|
|
PROG
|
(Axiom) -- (start)
)set expose add constructor OutputForm
pascal(0, n) == 1
pascal(n, n) == 1
pascal(i, j | 0 < i and i < j) == pascal(i-1, j-1) + pascal(i, j-1)
pascalRow(n) == [pascal(i, n) for i in 0..n]
displayRow(n) == output center blankSeparate pascalRow(n)
for i in 0..20 repeat displayRow i -- (end)
(Python) # See Hobson link. Further programs:
from math import prod, factorial
def C(n, k): return prod(range(n, n-k, -1))//factorial(k) # M. F. Hasler, Dec 13 2019, updated Apr 29 2022, Feb 17 2023
(Haskell)
a007318 n k = a007318_tabl !! n !! k
a007318_row n = a007318_tabl !! n
a007318_list = concat a007318_tabl
a007318_tabl = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Cf. http://www.haskell.org/haskellwiki/Blow_your_mind#Mathematical_sequences
(Maxima) create_list(binomial(n, k), n, 0, 12, k, 0, n); /* Emanuele Munarini, Mar 11 2011 */
(Sage) def C(n, k): return Subsets(range(n), k).cardinality() # Ralf Stephan, Jan 21 2014
(Magma) /* As triangle: */ [[Binomial(n, k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jul 29 2015
(GAP) Flat(List([0..12], n->List([0..n], k->Binomial(n, k)))); # Stefano Spezia, Dec 22 2018
|
|
|
CROSSREFS
|
Equals differences between consecutive terms of A102363. - David G. Williams (davidwilliams(AT)Paxway.com), Jan 23 2006
Row sums give A000079 (powers of 2).
Cf. A083093 (triangle read mod 3), A214292 (first differences of rows).
Partial sums of rows give triangle A008949.
The triangle of the antidiagonals is A011973.
Cf. A008277, A132311, A132312, A052216, A052217, A052218, A052219, A052220, A052221, A052222, A052223, A144225, A202750, A211226, A047999, A026729, A052553, A051920, A193242.
Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074, A228196, A228576.
Cf. A115940 (pandigital binomial coefficients C(m,k) with k>1).
Cf. (simplex colorings) A325002 (oriented), [k==n+1] (chiral), A325003 (achiral), A325000 (k or fewer colors), A325009 (orthotope facets, orthoplex vertices), A325017 (orthoplex facets, orthotope vertices).
Triangles of generalized binomial coefficients (n,k)_m (or generalized Pascal triangles) for m = 2..12: A001263, A056939, A056940, A056941, A142465, A142467, A142468, A174109, A342889, A342890, A342891.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Checked all links, deleted 8 that seemed lost forever and were probably not of great importance. - N. J. A. Sloane, May 08 2018
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000027
|
|
The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambiguous.
(Formerly M0472 N0173)
|
|
+10
2046
|
|
|
|
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For some authors, the terms "natural numbers" and "counting numbers" include 0, i.e., refer to the nonnegative integers A001477; the term "whole numbers" frequently also designates the whole set of (signed) integers A001057.
a(n) is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = n (cf. A007378).
Inverse Euler transform of A000219.
The rectangular array having A000027 as antidiagonals is the dispersion of the complement of the triangular numbers, A000217 (which triangularly form column 1 of this array). The array is also the transpose of A038722. - Clark Kimberling, Apr 05 2003
For nonzero x, define f(n) = floor(nx) - floor(n/x). Then f=A000027 if and only if x=tau or x=-tau. - Clark Kimberling, Jan 09 2005
If the offset were changed to 0, we would have the following pattern: a(n)=binomial(n,0) + binomial(n,1) for the present sequence (number of regions in 1-space defined by n points), A000124 (number of regions in 2-space defined by n straight lines), A000125 (number of regions in 3-space defined by n planes), A000127 (number of regions in 4-space defined by n hyperplanes), A006261, A008859, A008860, A008861, A008862 and A008863, where the last six sequences are interpreted analogously and in each "... by n ..." clause an offset of 0 has been assumed, resulting in a(0)=1 for all of them, which corresponds to the case of not cutting with a hyperplane at all and therefore having one region. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Define a number of points on a straight line to be in general arrangement when no two points coincide. Then these are the numbers of regions defined by n points in general arrangement on a straight line, when an offset of 0 is assumed. For instance, a(0)=1, since using no point at all leaves one region. The sequence satisfies the recursion a(n) = a(n-1) + 1. This has the following geometrical interpretation: Suppose there are already n-1 points in general arrangement, thus defining the maximal number of regions on a straight line obtainable by n-1 points, and now one more point is added in general arrangement. Then it will coincide with no other point and act as a dividing wall thereby creating one new region in addition to the a(n-1)=(n-1)+1=n regions already there, hence a(n)=a(n-1)+1. Cf. the comments on A000124 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
The sequence a(n)=n (for n=1,2,3) and a(n)=n+1 (for n=4,5,...) gives to the rank (minimal cardinality of a generating set) for the semigroup I_n\S_n, where I_n and S_n denote the symmetric inverse semigroup and symmetric group on [n]. - James East, May 03 2007
The sequence a(n)=n (for n=1,2), a(n)=n+1 (for n=3) and a(n)=n+2 (for n=4,5,...) gives the rank (minimal cardinality of a generating set) for the semigroup PT_n\T_n, where PT_n and T_n denote the partial transformation semigroup and transformation semigroup on [n]. - James East, May 03 2007
"God made the integers; all else is the work of man." This famous quotation is a translation of "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk," spoken by Leopold Kronecker in a lecture at the Berliner Naturforscher-Versammlung in 1886. Possibly the first publication of the statement is in Heinrich Weber's "Leopold Kronecker," Jahresberichte D.M.V. 2 (1893) 5-31. - Clark Kimberling, Jul 07 2007
Writing A000027 as N, perhaps the simplest one-to-one correspondence between N X N and N is this: f(m,n) = ((m+n)^2 - m - 3n + 2)/2. Its inverse is given by I(k)=(g,h), where g = k - J(J-1)/2, h = J + 1 - g, J = floor((1 + sqrt(8k - 7))/2). Thus I(1)=(1,1), I(2)=(1,2), I(3)=(2,1) and so on; the mapping I fills the first-quadrant lattice by successive antidiagonals. - Clark Kimberling, Sep 11 2008
a(n) is also the mean of the first n odd integers. - Ian Kent, Dec 23 2008
Equals INVERTi transform of A001906, the even-indexed Fibonacci numbers starting (1, 3, 8, 21, 55, ...). - Gary W. Adamson, Jun 05 2009
These are also the 2-rough numbers: positive integers that have no prime factors less than 2. - Michael B. Porter, Oct 08 2009
Totally multiplicative sequence with a(p) = p for prime p. Totally multiplicative sequence with a(p) = a(p-1) + 1 for prime p. - Jaroslav Krizek, Oct 18 2009
Triangle T(k,j) of natural numbers, read by rows, with T(k,j) = binomial(k,2) + j = (k^2-k)/2 + j where 1 <= j <= k. In other words, a(n) = n = binomial(k,2) + j where k is the largest integer such that binomial(k,2) < n and j = n - binomial(k,2). For example, T(4,1)=7, T(4,2)=8, T(4,3)=9, and T(4,4)=10. Note that T(n,n)=A000217(n), the n-th triangular number. - Dennis P. Walsh, Nov 19 2009
Hofstadter-Conway-like sequence (see A004001): a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = 1, a(2) = 2. - Jaroslav Krizek, Dec 11 2009
a(n) is also the dimension of the irreducible representations of the Lie algebra sl(2). - Leonid Bedratyuk, Jan 04 2010
Generated from a(2n) = r*a(n), a(2n+1) = a(n) + a(n+1), r = 2; in an infinite set, row 2 of the array shown in A178568. - Gary W. Adamson, May 29 2010
1/n = continued fraction [n]. Let barover[n] = [n,n,n,...] = 1/k. Then k - 1/k = n. Example: [2,2,2,...] = (sqrt(2) - 1) = 1/k, with k = (sqrt(2) + 1). Then 2 = k - 1/k. - Gary W. Adamson, Jul 15 2010
Number of n-digit numbers the binary expansion of which contains one run of 1's. - Vladimir Shevelev, Jul 30 2010
Let T denote the "natural number array A000027":
1 2 4 7 ...
3 5 8 12 ...
6 9 13 18 ...
10 14 19 25 ...
T(n,k) = n+(n+k-2)*(n+k-1)/2. See A185787 for a list of sequences based on T, such as rows, columns, diagonals, and sub-arrays. (End)
The Stern polynomial B(n,x) evaluated at x=2. See A125184. - T. D. Noe, Feb 28 2011
The denominator in the Maclaurin series of log(2), which is 1 - 1/2 + 1/3 - 1/4 + .... - Mohammad K. Azarian, Oct 13 2011
As a function of Bernoulli numbers B_n (cf. A027641: (1, -1/2, 1/6, 0, -1/30, 0, 1/42, ...)): let V = a variant of B_n changing the (-1/2) to (1/2). Then triangle A074909 (the beheaded Pascal's triangle) * [1, 1/2, 1/6, 0, -1/30, ...] = the vector [1, 2, 3, 4, 5, ...]. - Gary W. Adamson, Mar 05 2012
Number of partitions of 2n+1 into exactly two parts. - Wesley Ivan Hurt, Jul 15 2013
Integers n dividing u(n) = 2u(n-1) - u(n-2); u(0)=0, u(1)=1 (Lucas sequence A001477). - Thomas M. Bridge, Nov 03 2013
For this sequence, the generalized continued fraction a(1)+a(1)/(a(2)+a(2)/(a(3)+a(3)/(a(4)+...))), evaluates to 1/(e-2) = A194807. - Stanislav Sykora, Jan 20 2014
a(n) is the number of permutations of length n simultaneously avoiding 213, 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
a(n) 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
a(n) = least k such that 2*Pi - Sum_{h=1..k} 1/(h^2 - h + 3/16) < 1/n. - Clark Kimberling, Sep 28 2014
a(n) = least k such that Pi^2/6 - Sum_{h=1..k} 1/h^2 < 1/n. - Clark Kimberling, Oct 02 2014
Determinants of the spiral knots S(2,k,(1)). a(k) = det(S(2,k,(1))). These knots are also the torus knots T(2,k). - Ryan Stees, Dec 15 2014
As a function, the restriction of the identity map on the nonnegative integers {0,1,2,3...}, A001477, to the positive integers {1,2,3,...}. - M. F. Hasler, Jan 18 2015
See also A131685(k) = smallest positive number m such that c(i) = m (i^1 + 1) (i^2 + 2) ... (i^k+ k) / k! takes integral values for all i>=0: For k=1, A131685(k)=1, which implies that this is a well defined integer sequence. - Alexander R. Povolotsky, Apr 24 2015
a(n) is the number of compositions of n+2 into n parts avoiding the part 2. - Milan Janjic, Jan 07 2016
Does not satisfy Benford's law [Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
For n >= 3, a(n)=n is the least area that can be obtained for an irregular octagon drawn in a square of n units side, whose sides are parallel to the axes, with 4 vertices that coincide with the 4 vertices of the square, and the 4 remaining vertices having integer coordinates. See Affaire de Logique link. - Michel Marcus, Apr 28 2018
a(n+1) is the order of rowmotion on a poset defined by a disjoint union of chains of length n. - Nick Mayers, Jun 08 2018
Number of 1's in n-th generation of 1-D Cellular Automata using Rules 50, 58, 114, 122, 178, 186, 206, 220, 238, 242, 250 or 252 in the Wolfram numbering scheme, started with a single 1. - Frank Hollstein, Mar 25 2019
(1, 2, 3, 4, 5, ...) is the fourth INVERT transform of (1, -2, 3, -4, 5, ...). - Gary W. Adamson, Jul 15 2019
|
|
|
REFERENCES
|
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 1.
T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer-Verlag, 1990, page 25.
W. Fulton and J. Harris, Representation theory: a first course, (1991), page 149. [From Leonid Bedratyuk, Jan 04 2010]
I. S. Gradstein and I. M. Ryshik, Tables of series, products, and integrals, Volume 1, Verlag Harri Deutsch, 1981.
R. E. Schwartz, You Can Count on Monsters: The First 100 numbers and Their Characters, A. K. Peters and MAA, 2010.
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
|
N. Brothers, S. Evans, L. Taalman, L. Van Wyk, D. Witczak, and C. Yarnall, Spiral knots, Missouri J. of Math. Sci., 22 (2010).
M. DeLong, M. Russell, and J. Schrock, Colorability and determinants of T(m,n,r,s) twisted torus knots for n equiv. +/-1(mod m), Involve, Vol. 8 (2015), No. 3, 361-384.
Eric Weisstein's World of Mathematics, Natural Number, Positive Integer, Counting Number Composition, Davenport-Schinzel Sequence, Idempotent Number, N, Smarandache Ceil Function, Whole Number, Engel Expansion, and Trinomial Coefficient
|
|
|
FORMULA
|
Another g.f.: Sum_{n>0} phi(n)*x^n/(1-x^n) (Apostol).
When seen as an array: T(k, n) = n+1 + (k+n)*(k+n+1)/2. Main diagonal is 2n*(n+1)+1 (A001844), antidiagonal sums are n*(n^2+1)/2 (A006003). - Ralf Stephan, Oct 17 2004
G.f.: x/(1-x)^2. E.g.f.: x*exp(x). a(n)=n. a(-n)=-a(n).
Series reversion of g.f. A(x) is x*C(-x)^2 where C(x) is the g.f. of A000108. - Michael Somos, Sep 04 2006
G.f. A(x) satisfies 0 = f(A(x), A(x^2)) where f(u, v) = u^2 - v - 4*u*v. - Michael Somos, Oct 03 2006
a(n) = 2*a(n-1)-a(n-2); a(1)=1, a(2)=2. a(n) = 1+a(n-1). - Philippe Deléham, Nov 03 2008
G.f.: x * Product_{j>=0} (1+x^(2^j))^2 = x * (1+2*x+x^2) * (1+2*x^2+x^4) * (1+2*x^4+x^8) * ... = x + 2x^2 + 3x^3 + ... . - Gary W. Adamson, Jun 26 2012
a(n) = det(binomial(i+1,j), 1 <= i,j <= n). - Mircea Merca, Apr 06 2013
E.g.f.: x*E(0), where E(k) = 1 + 1/(x - x^3/(x^2 + (k+1)/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 03 2013
a(n) = Product_{k=1..n-1} 2*sin(Pi*k/n), n > 1.
a(n) = Product_{k=1..n-1} (2*sin(Pi*k/(2*n)))^2, n > 1.
These identities are used in the calculation of products of ratios of lengths of certain lines in a regular n-gon. For the first identity see the Gradstein-Ryshik reference, p. 62, 1.392 1., bringing the first factor there to the left hand side and taking the limit x -> 0 (L'Hôpital). The second line follows from the first one. Thanks to Seppo Mustonen who led me to consider n-gon lengths products. (End)
a(n) = Sum_{j=0..k} (-1)^(j-1)*j*binomial(n,j)*binomial(n-1+k-j,k-j), k>=0. - Mircea Merca, Jan 25 2014
a(n) = Sum_{k=1..n^2+2*n} 1/(sqrt(k)+sqrt(k+1)). - Pierre CAMI, Apr 25 2014
a(n) = floor(1/sin(1/n)) = floor(cot(1/(n+1))) = ceiling(cot(1/n)). - Clark Kimberling, Oct 08 2014
a(n) = 1/(1/(n+1) + 1/(n+1)^2 + 1/(n+1)^3 + ...). - Pierre CAMI, Jan 22 2015
a(n) = Sum_{m=0..n-1} Stirling1(n-1,m)*Bell(m+1), for n >= 1. This corresponds to Bell(m+1) = Sum_{k=0..m} Stirling2(m, k)*(k+1), for m >= 0, from the fact that Stirling2*Stirling1 = identity matrix. See A048993, A048994 and A000110. - Wolfdieter Lang, Feb 03 2015
a(n) = Sum_{k=1..2n-1}(-1)^(k+1)*k*(2n-k). In addition, surprisingly, a(n) = Sum_{k=1..2n-1}(-1)^(k+1)*k^2*(2n-k)^2. - Charlie Marion, Jan 05 2016
G.f.: x/(1-x)^2 = (x * r(x) *r(x^3) * r(x^9) * r(x^27) * ...), where r(x) = (1 + x + x^2)^2 = (1 + 2x + 3x^2 + 2x^3 + x^4). - Gary W. Adamson, Jan 11 2017
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(Magma) [ n : n in [1..100]];
(PARI) {a(n) = n};
(R) 1:100
(Shell) seq 1 100
(Haskell)
a000027 = id
(Maxima) makelist(n, n, 1, 30); /* Martin Ettl, Nov 07 2012 */
(Python)
|
|
|
CROSSREFS
|
Cf. A026081 = integers in reverse alphabetical order in U.S. English, A107322 = English name for number and its reverse have the same number of letters, A119796 = zero through ten in alphabetical order of English reverse spelling, A005589, etc. Cf. A185787 (includes a list of sequences based on the natural number array A000027).
Cf. A038722 (mirrored when seen as triangle), A056011 (boustrophedon).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Links edited by _Daniel Forgues_, Oct 07 2009
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.509 seconds
|
