Displaying 1-10 of 82 results found.
Integers of the form p^2*q in A120806: x+d+1 is prime for all divisors d of x. Both p and q are odd primes, with p and q distinct. See A054753.
+20
3
1859, 331169, 2141399, 4641629, 6633419, 8447039, 10338119, 13526009, 20163059, 21603425, 24099569, 26187119, 26483321, 28226549, 33379569, 33485139, 40790009, 50139819, 52046075, 56152179, 57170075, 59824925, 72541799, 81638579, 104151839, 106624359, 106791269
EXAMPLE
a(1) = 1859 since x = 11*13^2, divisors(x) = {1, 11, 13, 11*13, 13^2, 11*13^2} and x+d+1 = {1861, 1871, 1873, 2003, 2029, 3719} are all primes.
MAPLE
with(numtheory); is3almostprime := proc(n) local L; if n in [0, 1] or isprime(n) then return false fi; L:=ifactors(n)[2]; if nops(L) in [1, 2, 3] and convert(map(z-> z[2], L), `+`) = 3 then return true else return false fi; end; L:=[]: for w to 1 do for k from 1 while nops(L)<=50 do x:=2*k+1; y:=simplify(x^(1/3)); if x mod 6 = 5 and not type(y, integer) #clunky and not issqrfree(x) and is3almostprime(x) and andmap(isprime, [x+2, 2*x+1]) then S:=divisors(x); Q:=map(z-> x+z+1, S); if andmap(isprime, Q) then L:=[op(L), x]; print(nops(L), ifactor(x)); fi; fi; od od;
PROG
(PARI) is(n) = my(f); if(!(n%2), return(0)); f = factor(n); if(f[, 2] != [1, 2]~ && f[, 2] != [2, 1]~, return(0)); fordiv(f, d, if(!isprime(n + d + 1), return(0))); 1; \\ Amiram Eldar, Aug 05 2024
EXTENSIONS
a(2) corrected and a(24)-a(27) added by Amiram Eldar, Aug 05 2024
a(n) = 1 if n is either 4th power of a prime ( A030514), or product of a prime and the square of a different prime ( A054753), otherwise 0.
+20
1
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0
FORMULA
a(n) = [floor( A101296(n)/2) == 3], where [ ] is the Iverson bracket, giving in this case 1 only if the prime signature class of n ( A101296) is either 6 or 7.
MATHEMATICA
a[n_] := If[MemberQ[{{4}, {1, 2}, {2, 1}}, FactorInteger[n][[;; , 2]]], 1, 0]; Array[a, 100] (* Amiram Eldar, May 13 2022 *)
PROG
(PARI) A353798(n) = { my(f=factor(n)[, 2]~); (f==[4] || f==[2, 1] || f==[1, 2]); }; \\ From function "is" in A080258
CROSSREFS
Characteristic function of A080258.
Hexagonal numbers: a(n) = n*(2*n-1).
(Formerly M4108 N1705)
+10
442
0, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, 378, 435, 496, 561, 630, 703, 780, 861, 946, 1035, 1128, 1225, 1326, 1431, 1540, 1653, 1770, 1891, 2016, 2145, 2278, 2415, 2556, 2701, 2850, 3003, 3160, 3321, 3486, 3655, 3828, 4005, 4186, 4371, 4560
COMMENTS
Number of edges in the join of two complete graphs, each of order n, K_n * K_n. - Roberto E. Martinez II, Jan 07 2002 The power series expansion of the entropy function H(x) = (1+x)log(1+x) + (1-x)log(1-x) has 1/a_i as the coefficient of x^(2i) (the odd terms being zero). - Tommaso Toffoli (tt(AT)bu.edu), May 06 2002
Sequence also gives the greatest semiperimeter of primitive Pythagorean triangles having inradius n-1. Such a triangle has consecutive longer sides, with short leg 2n-1, hypotenuse a(n) - (n-1) = A001844(n), and area (n-1)*a(n) = 6* A000330(n-1). - Lekraj Beedassy, Apr 23 2003 More generally, if p1 and p2 are two arbitrarily chosen distinct primes then a(n) is the number of divisors of (p1^2*p2)^(n-1) or equivalently of any member of A054753^(n-1). - Ant King, Aug 29 2011 Number of standard tableaux of shape (2n-1,1,1) (n>=1). - Emeric Deutsch, May 30 2004 It is well known that for n>0, A014105(n) [0,3,10,21,...] is the first of 2n+1 consecutive integers such that the sum of the squares of the first n+1 such integers is equal to the sum of the squares of the last n; e.g., 10^2 + 11^2 + 12^2 = 13^2 + 14^2. Less well known is that for n>1, a(n) [0,1,6,15,28,...] is the first of 2n consecutive integers such that sum of the squares of the first n such integers is equal to the sum of the squares of the last n-1 plus n^2; e.g., 15^2 + 16^2 + 17^2 = 19^2 + 20^2 + 3^2. - Charlie Marion, Dec 16 2006 Sequence found by reading the line from 0, in the direction 0, 6, ... and the line from 1, in the direction 1, 15, ..., in the square spiral whose vertices are the generalized hexagonal numbers A000217. - Omar E. Pol, Jan 09 2009 Let Hex(n)=hexagonal number, T(n)=triangular number, then Hex(n)=T(n)+3*T(n-1). - Vincenzo Librandi, Nov 10 2010 For n>=1, 1/a(n) = Sum_{k=0..2*n-1} ((-1)^(k+1)*binomial(2*n-1,k)*binomial(2*n-1+k,k)*H(k)/(k+1)) with H(k) harmonic number of order k.
The number of possible distinct colorings of any 2 colors chosen from n colors of a square divided into quadrants. - Paul Cleary, Dec 21 2010 For n>0, a(n-1) is the number of triples (w,x,y) with all terms in {0,...,n} and max(|w-x|,|x-y|) = |w-y|. - Clark Kimberling, Jun 12 2012 a(n) is the number of positions of one domino in an even pyramidal board with base 2n. - César Eliud Lozada, Sep 26 2012 Let a triangle have T(0,0) = 0 and T(r,c) = |r^2 - c^2|. The sum of the differences of the terms in row(n) and row(n-1) is a(n). - J. M. Bergot, Jun 17 2013 With T_(i+1,i)=a(i+1) and all other elements of the lower triangular matrix T zero, T is the infinitesimal generator for A176230, analogous to A132440 for the Pascal matrix. - Tom Copeland, Dec 11 2013 a(n) is the number of length 2n binary sequences that have exactly two 1's. a(2) = 6 because we have: {0,0,1,1}, {0,1,0,1}, {0,1,1,0}, {1,0,0,1}, {1,0,1,0}, {1,1,0,0}. The ordinary generating function with interpolated zeros is: (x^2 + 3*x^4)/(1-x^2)^3. - Geoffrey Critzer, Jan 02 2014 For n > 0, a(n) is the largest integer k such that k^2 + n^2 is a multiple of k + n. More generally, for m > 0 and n > 0, the largest integer k such that k^(2*m) + n^(2*m) is a multiple of k + n is given by k = 2*n^(2*m) - n. - Derek Orr, Sep 04 2014 Binomial transform of (0, 1, 4, 0, 0, 0, ...) and second partial sum of (0, 1, 4, 4, 4, ...). - Gary W. Adamson, Oct 05 2015 a(n) also gives the dimension of the simple Lie algebras D_n, for n >= 4. - Wolfdieter Lang, Oct 21 2015 For n > 0, a(n) equals the number of compositions of n+11 into n parts avoiding parts 2, 3, 4. - Milan Janjic, Jan 07 2016 Also the number of minimum dominating sets and maximal irredundant sets in the n-cocktail party graph. - Eric W. Weisstein, Jun 29 and Aug 17 2017 As Beedassy's formula shows, this Hexagonal number sequence is the odd bisection of the Triangle number sequence. Both of these sequences are figurative number sequences. For A000384, a(n) can be found by multiplying its triangle number by its hexagonal number. For example let's use the number 153. 153 is said to be the 17th triangle number but is also said to be the 9th hexagonal number. Triangle(17) Hexagonal(9). 17*9=153. Because the Hexagonal number sequence is a subset of the Triangle number sequence, the Hexagonal number sequence will always have both a triangle number and a hexagonal number. n* (2*n-1) because (2*n-1) renders the triangle number. - Bruce J. Nicholson, Nov 05 2017 Also numbers k with the property that in the symmetric representation of sigma(k) the smallest Dyck path has a central valley and the largest Dyck path has a central peak, n >= 1. Thus all hexagonal numbers > 0 have middle divisors. (Cf. A237593.) - Omar E. Pol, Aug 28 2018 Consider all Pythagorean triples (X, Y, Z=Y+1) ordered by increasing Z: a(n+1) gives the semiperimeter of related triangles; A005408, A046092 and A001844 give the X, Y and Z values. - Ralf Steiner, Feb 25 2020 It appears that these are the numbers k with the property that the smallest subpart in the symmetric representation of sigma(k) is 1. - Omar E. Pol, Aug 28 2021 The n-th hexagonal number equals the sum of the n consecutive integers with the same parity starting at 2*n-1; for example, 1, 2+4, 3+5+7, 4+6+8+10, etc. In general, the n-th 2k-gonal number is the sum of the n consecutive integers with the same parity starting at (k-2)*n - (k-3). When k = 1 and 2, this result generates the positive integers, A000027, and the squares, A000290, respectively. - Charlie Marion, Mar 02 2022 Conjecture: For n>0, min{k such that there exist subsets A,B of {0,1,2,...,a(n)} such that |A|=|B|=k and A+B={0,1,2,...,2*a(n)}} = 2*n. - Michael Chu, Mar 09 2022
REFERENCES
Albert H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 189.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, pp. 77-78. (In the integral formula on p. 77 a left bracket is missing for the cosine argument.)
E. Deza and M. M. Deza, Figurate numbers, World Scientific Publishing (2012), page 6.
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. 2, p. 2.
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).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See pp. 122-123.
LINKS
Jonathan M. Borwein, Dirk Nuyens, Armin Straub and James Wan, Random Walk Integrals, The Ramanujan Journal, October 2011, 26:109. DOI: 10.1007/s11139-011-9325-y. Michel Waldschmidt, Continued fractions, Ecole de recherche CIMPA-Oujda, Théorie des Nombres et ses Applications, 18 - 29 mai 2015: Oujda (Maroc).
FORMULA
E.g.f.: exp(x)*(x+2x^2). - Paul Barry, Jun 09 2003 G.f.: x*(1+3*x)/(1-x)^3. - Simon Plouffe in his 1992 dissertation, dropping the initial zero a(n) = right term of M^n * [1,0,0], where M = the 3 X 3 matrix [1,0,0; 1,1,0; 1,4,1]. Example: a(5) = 45 since M^5 *[1,0,0] = [1,5,45]. - Gary W. Adamson, Dec 24 2006 Starting with offset 1, = binomial transform of [1, 5, 4, 0, 0, 0, ...]. Also, A004736 * [1, 4, 4, 4, ...]. - Gary W. Adamson, Oct 25 2007 a(n)^2 + (a(n)+1)^2 + ... + (a(n)+n-1)^2 = (a(n)+n+1)^2 + ... + (a(n)+2n-1)^2 + n^2; e.g., 6^2 + 7^2 = 9^2 + 2^2; 28^2 + 29^2 + 30^2 + 31^2 = 33^2 + 34^2 + 35^2 + 4^2. - Charlie Marion, Nov 10 2007 a(n) = binomial(n+1,2) + 3*binomial(n,2).
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3), a(0)=0, a(1)=1, a(2)=6. - Jaume Oliver Lafont, Dec 02 2008 a(n) = 2*a(n-1) - a(n-2) + 4. - Ant King, Aug 26 2011 a(n+1) = trinomial(2*n+1, 2) = trinomial(2*n+1, 4*n), for n >= 0, with the trinomial irregular triangle A027907. a(n+1) = (n+1)*(2*n+1) = (1/Pi)*Integral_{x=0..2} (1/sqrt(4 - x^2))*(x^2 - 1)^(2*n+1)*R(4*n-2, x) with the R polynomial coefficients given in A127672. [Comtet, p. 77, the integral formula for q=3, n -> 2*n+1, k = 2, rewritten with x = 2*cos(phi)]. - Wolfdieter Lang, Apr 19 2018 Product_{n>=2} (1 - 1/a(n)) = 2/3. - Amiram Eldar, Jan 21 2021 a(n) = floor(Sum_{k=(n-1)^2..n^2} sqrt(k)), for n >= 1. - Amrit Awasthi, Jun 13 2021
MATHEMATICA
LinearRecurrence[{3, -3, 1}, {0, 1, 6}, 50] (* Harvey P. Dale, Sep 10 2015 *) Join[{0}, Accumulate[Range[1, 312, 4]]] (* Harvey P. Dale, Mar 26 2016 *) (* For Mathematica 10.4+ *) Table[PolygonalNumber[RegularPolygon[6], n], {n, 0, 48}] (* Arkadiusz Wesolowski, Aug 27 2016 *) CoefficientList[Series[x*(1 + 3*x)/(1 - x)^3 , {x, 0, 100}], x] (* Stefano Spezia, Sep 02 2018 *)
PROG
(PARI) a(n)=n*(2*n-1)
(PARI) a(n) = binomial(2*n, 2) \\ Altug Alkan, Oct 06 2015 (Haskell)
a000384 n = n * (2 * n - 1)
a000384_list = scanl (+) 0 a016813_list
(Python) # Intended to compute the initial segment of the sequence, not isolated terms.
def aList():
x, y = 1, 1
yield 0
while True:
yield x
x, y = x + y + 4, y + 4
CROSSREFS
a(n)= A093561(n+1, 2), (4, 1)-Pascal column. Cf. A002939 (twice a(n): sums of Pythagorean triples (X, Y, Z=Y+1)).
Number of Abelian groups of order n; number of factorizations of n into prime powers.
(Formerly M0064 N0020)
+10
130
1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 2, 2, 1, 1, 1, 5, 5, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 7, 1, 2, 2, 4, 1, 1, 1, 3, 1, 1, 1
COMMENTS
Equivalently, number of Abelian groups with n conjugacy classes. - Michael Somos, Aug 10 2010 a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1). Also number of rings with n elements that are the direct product of fields; these are the commutative rings with n elements having no nilpotents; likewise the commutative rings where for every element x there is a k > 0 such that x^(k+1) = x. - Franklin T. Adams-Watters, Oct 20 2006 a(n) = 1 if and only if n is from A005117 (squarefree numbers). See the Ahmed Fares comment there, and the formula for n>=2 below. - Wolfdieter Lang, Sep 09 2012 Also, from a theorem of Molnár (see [Molnár]), the number of (non-isomorphic) abelian groups of order 2*n + 1 is equal to the number of non-congruent lattice Z-tilings of R^n by crosses, where a "cross" is a unit cube in R^n for which at each facet is attached another unit cube (Z, R are the integers and reals, respectively). (Cf. [Horak].) - L. Edson Jeffery, Nov 29 2012 Zeta(k*s) is the Dirichlet generating function of the characteristic function of numbers which are k-th powers (k=1 in A000012, k=2 in A010052, k=3 in A010057, see arXiv:1106.4038 Section 3.1). The infinite product over k (here) is the number of representations n=product_i (b_i)^(e_i) where all exponents e_i are distinct and >=1. Examples: a(n=4)=2: 4^1 = 2^2. a(n=8)=3: 8^1 = 2^1*2^2 = 2^3. a(n=9)=2: 9^1 = 3^2. a(n=12)=2: 12^1 = 3*2^2. a(n=16)=5: 16^1 = 2*2^3 = 4^2 = 2^2*4^1 = 2^4. If the e_i are the set {1,2} we get A046951, the number of representations as a product of a number and a square. - R. J. Mathar, Nov 05 2016
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 274-278.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIII.12, p. 468.
J. S. Rose, A Course on Group Theory, Camb. Univ. Press, 1978, see p. 7.
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).
A. Speiser, Die Theorie der Gruppen von endlicher Ordnung, 4. Auflage, Birkhäuser, 1956.
FORMULA
Multiplicative with a(p^k) = number of partitions of k = A000041(k); a(mn) = a(m)a(n) if (m, n) = 1. a(n) = Product_{j = 1..N(n)} A000041(e(j)), n >= 2, if n = Product_{j = 1..N(n)} prime(j)^e(j), N(n) = A001221(n). See the Richert reference, quoting A. Speiser's book on finite groups (in German, p. 51 in words). - Wolfdieter Lang, Jul 23 2011 In terms of the cycle index of the symmetric group: Product_{q=1..m} [z^{v_q}] Z(S_v) 1/(1-z) where v is the maximum exponent of any prime in the prime factorization of n, v_q are the exponents of the prime factors, and Z(S_v) is the cycle index of the symmetric group on v elements. - Marko Riedel, Oct 03 2014 Dirichlet g.f.: Sum_{n >= 1} a(n)/n^s = Product_{k >= 1} zeta(ks) [Kendall]. - Álvar Ibeas, Nov 05 2014 Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A021002. (End)
EXAMPLE
a(1) = 1 since the trivial group {e} is the only group of order 1, and it is Abelian; alternatively, since the only factorization of 1 into prime powers is the empty product.
a(p) = 1 for any prime p, since the only factorization into prime powers is p = p^1, and (in view of Lagrange's theorem) there is only one group of prime order p; it is isomorphic to (Z/pZ,+) and thus Abelian.
a(8) = 3 because 8 = 2^3, hence a(8) = pa(3) = A000041(3) = 3 from the partitions (3), (2, 1) and (1, 1, 1), leading to the 3 factorizations of 8: 8, 4*2 and 2*2*2. a(36) = 4 because 36 = 2^2*3^2, hence a(36) = pa(2)*pa(2) = 4 from the partitions (2) and (1, 1), leading to the 4 factorizations of 36: 2^2*3^2, 2^2*3^1*3^1, 2^1*2^1*3^2 and 2^1*2^1*3^1*3^1.
(End)
MAPLE
with(combinat): readlib(ifactors): for n from 1 to 120 do ans := 1: for i from 1 to nops(ifactors(n)[2]) do ans := ans*numbpart(ifactors(n)[2][i][2]) od: printf(`%d, `, ans): od: # James A. Sellers, Dec 07 2000
MATHEMATICA
f[n_] := Times @@ PartitionsP /@ Last /@ FactorInteger@n; Array[f, 107] (* Robert G. Wilson v, Sep 22 2006 *)
PROG
(Sage)
def a(n):
F=factor(n)
return prod([number_of_partitions(F[i][1]) for i in range(len(F))])
(Haskell)
a000688 = product . map a000041 . a124010_row
(Python)
from sympy import factorint, npartitions
from math import prod
def A000688(n): return prod(map(npartitions, factorint(n).values())) # Chai Wah Wu, Jan 14 2022
CROSSREFS
Cf. A000001, A021002, A060689, A000041, A000961, A001055, A005361, A034382, A046054, A046055, A046056, A046101, A050360, A055653, A057521, A101872 (bisection), A101876 (quadrisection), A124010, A050361, A051532, A129667 (Dirichlet inverse).
n has the a(n)-th distinct prime signature.
+10
109
1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 5, 6, 2, 9, 2, 10, 4, 4, 4, 11, 2, 4, 4, 8, 2, 9, 2, 6, 6, 4, 2, 12, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 13, 2, 4, 6, 14, 4, 9, 2, 6, 4, 9, 2, 15, 2, 4, 6, 6, 4, 9, 2, 12, 7, 4, 2, 13, 4, 4, 4, 8, 2, 13, 4, 6, 4, 4, 4, 16, 2, 6, 6, 11, 2, 9, 2, 8, 9, 4, 2, 15, 2, 9, 4, 12, 2, 9, 4, 6, 6, 4, 4, 17
COMMENTS
Restricted growth sequence transform of A046523, the least representative of each prime signature. Thus this partitions the natural numbers to the same equivalence classes as A046523, i.e., for all i, j: a(i) = a(j) <=> A046523(i) = A046523(j), and for that reason satisfies in that respect all the same conditions as A046523. For example, we have, for all i, j: if a(i) = a(j), then: So, this sequence (instead of A046523) can be used for finding sequences where a(n)'s value is dependent only on the prime signature of n, that is, only on the multiset of prime exponents in the factorization of n. (End) This is also the restricted growth sequence transform of many other sequences, for example, that of A181819. See further comments there. - Antti Karttunen, Apr 30 2022
FORMULA
From David A. Corneth, May 12 2017: (Start) [Corresponding characteristic function in brackets] a( A085987(n)) = 13 (sig.: (1,1,2)). a( A189975(n)) = 17 (sig.: (1,1,3)). a( A179643(n)) = 20 (sig.: (1,2,2)). a( A046386(n)) = 22 (sig.: (1,1,1,1)). a( A162142(n)) = 23 (sig.: (2,2,2)). a( A179644(n)) = 24 (sig.: (1,1,4)). a( A163569(n)) = 27 (sig.: (1,2,3)). a( A189982(n)) = 29 (sig.: (1,1,1,2)). a( A179667(n)) = 31 (sig.: (1,1,5)). a( A179669(n)) = 34 (sig.: (1,2,4)). a( A179670(n)) = 36 (sig.: (1,1,1,3)). a( A162143(n)) = 38 (sig.: (2,2,2)). a( A179672(n)) = 39 (sig.: (1,1,6)). a( A179688(n)) = 41 (sig.: (1,3,3)). a( A179690(n)) = 43 (sig.: (1,1,2,2)). a( A179691(n)) = 45 (sig.: (1,2,5)). a( A179693(n)) = 47 (sig.: (1,1,1,4)). a( A179695(n)) = 49 (sig.: (2,2,3)). a( A179696(n)) = 50 (sig.: (1,1,7)). (End)
EXAMPLE
1 has prime signature (), the first distinct prime signature. Therefore, a(1) = 1.
2 has prime signature (1), the second distinct prime signature after (1). Therefore, a(2) = 2.
3 has prime signature (1), as does 2. Therefore, a(3) = a(2) = 2.
4 has prime signature (2), the third distinct prime signature after () and (1). Therefore, a(4) = 3. (End)
Construction of restricted growth sequences: In this case we start with a(1) = 1 for A046523(1) = 1, and thereafter, for all n > 1, we use the least so far unused natural number k for a(n) if A046523(n) has not been encountered before, otherwise [whenever A046523(n) = A046523(m), for some m < n], we set a(n) = a(m). For n = 2, A046523(2) = 2, which has not been encountered before (first prime), thus we allot for a(2) the least so far unused number, which is 2, thus a(2) = 2. For n = 3, A046523(2) = 2, which was already encountered as A046523(1), thus we set a(3) = a(2) = 2. For n = 4, A046523(4) = 4, not encountered before (first square of prime), thus we allot for a(4) the least so far unused number, which is 3, thus a(4) = 3. For n = 5, A046523(5) = 2, as for the first time encountered at n = 2, thus we set a(5) = a(2) = 2. For n = 6, A046523(6) = 6, not encountered before (first semiprime pq with distinct p and q), thus we allot for a(6) the least so far unused number, which is 4, thus a(6) = 4. For n = 8, A046523(8) = 8, not encountered before (first cube of a prime), thus we allot for a(8) the least so far unused number, which is 5, thus a(8) = 5. For n = 9, A046523(9) = 4, as for the first time encountered at n = 4, thus a(9) = 3. (End)
(Rough) description of an algorithm of computing the sequence:
Suppose we want to compute a(n) for n in [1..20].
We set up a vector of 20 elements, values 0, and a number m = 1, the minimum number we haven't checked and c = 0, the number of distinct prime signatures we've found so far.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
We check the prime signature of m and see that it's (). We increase c with 1 and set all elements up to 20 with prime signature () to 1. In the process, we adjust m. This gives:
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The least number we haven't checked is m = 2. 2 has prime signature (1). We increase c with 1 and set all elements up to 20 with prime signature (1) to 2. In the process, we adjust m. This gives:
[1, 2, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
We check the prime signature of m = 4 and see that its prime signature is (2). We increase c with 1 and set all numbers up to 20 with prime signature (2) to 3. This gives:
[1, 2, 2, 3, 2, 0, 2, 0, 3, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0]
Similarily, after m = 6, we get
[1, 2, 2, 3, 2, 4, 2, 0, 3, 4, 2, 0, 2, 4, 4, 0, 2, 0, 2, 0], after m = 8 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 0, 2, 4, 4, 0, 2, 0, 2, 0], after m = 12 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 0, 2, 6, 2, 0], after m = 16 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 0], after m = 20 we get:
[1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 6, 2, 8]. Now, m > 20 so we stop. (End)
The above method is inefficient, because the step "set all elements a(n) up to n = Nmax with prime signature s(n) = S[c] to c" requires factoring all integers up to Nmax (or at least comparing their signature, once computed, with S[c]) again and again. It is much more efficient to run only once over each m = 1..Nmax, compute its prime signature s(m), add it to an ordered list in case it did not occur earlier, together with its "rank" (= new size of the list), and assign that rank to a(m). The list of prime signatures is much shorter than [1..Nmax]. One can also use m'(m) := the smallest n with the prime signature of m (which is faster to compute than to search for the signature) as representative for s(m), and set a(m) := a(m'(m)). Then it is sufficient to have just one counter (number of prime signatures seen so far) as auxiliary variable, in addition to the sequence to be computed. - M. F. Hasler, Jul 18 2019
MAPLE
local a046523, a;
for a from 1 do
return a;
return -1 ;
end if;
end do:
MATHEMATICA
With[{nn = 120}, Function[s, Table[Position[Keys@s, k_ /; MemberQ[k, n]][[1, 1]], {n, nn}]]@ Map[#1 -> #2 & @@ # &, Transpose@ {Values@ #, Keys@ #}] &@ PositionIndex@ Table[Times @@ MapIndexed[Prime[First@ #2]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]] - Boole[n == 1], {n, nn}] ] (* Michael De Vlieger, May 12 2017, Version 10 *)
PROG
(PARI) find(ps, vps) = {for (k=1, #vps, if (vps[k] == ps, return(k)); ); }
lisps(nn) = {vps = []; for (n=1, nn, ps = vecsort(factor(n)[, 2]); ips = find(ps, vps); if (! ips, vps = concat(vps, ps); ips = #vps); print1(ips, ", "); ); } \\ Michel Marcus, Nov 15 2015; edited by M. F. Hasler, Jul 16 2019 (PARI)
rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences, invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences, invec[i], i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset, vec, bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
write_to_bfile(1, rgs_transform(vector(100000, n, A046523(n))), "b101296.txt");
CROSSREFS
Sequences that are unions of finite number (>= 2) of equivalence classes determined by the values that this sequence obtains (i.e., sequences mentioned in David A. Corneth's May 12 2017 formula): A001358 ( A001248 U A006881, values 3 & 4), A007422 (values 1, 4, 5), A007964 (2, 3, 4, 5), A014612 (5, 6, 9), A030513 (4, 5), A037143 (1, 2, 3, 4), A037144 (1, 2, 3, 4, 5, 6, 9), A080258 (6, 7), A084116 (2, 4, 5), A167171 (2, 4), A217856 (6, 9). Cf. also A077462, A305897 (stricter variants, with finer partitioning) and A254524, A286603, A286605, A286610, A286619, A286621, A286622, A286626, A286378 for other similarly constructed sequences.
Squares of the squarefree semiprimes (p^2*q^2).
+10
45
36, 100, 196, 225, 441, 484, 676, 1089, 1156, 1225, 1444, 1521, 2116, 2601, 3025, 3249, 3364, 3844, 4225, 4761, 5476, 5929, 6724, 7225, 7396, 7569, 8281, 8649, 8836, 9025, 11236, 12321, 13225, 13924, 14161, 14884, 15129, 16641, 17689, 17956, 19881
COMMENTS
This sequence is a member of a family of sequences directly related to A025487. First terms and known sequences are listed below: 1, A000007; 2, A000040; 4, A001248; 6, A006881; 8, A030078; 12, A054753; 16, A030514; 24, A065036; 30, A007304; 32, A050997; 36, this sequence; 48, ?; 60, ?; 64, ?; .... a(4)-a(3)=29 and a(3)+a(4)=421 are both prime. There are no other cases where the sum and difference of two members of this sequence are both prime. - Robert Israel and J. M. Bergot, Oct 25 2019
FORMULA
Sum_{n>=1} 1/a(n) = (P(2)^2 - P(4))/2 = ( A085548^2 - A085964)/2 = 0.063767..., where P is the prime zeta function. - Amiram Eldar, Jul 06 2020
EXAMPLE
A006881 begins 6 10 14 15 ... so this sequence begins 36 100 196 225 ...
MATHEMATICA
Select[Range[200], PrimeOmega[#]==2&&SquareFreeQ[#]&]^2 (* Harvey P. Dale, Mar 07 2013 *)
PROG
(PARI) list(lim)=my(v=List(), x=sqrtint(lim\=1), t); forprime(p=2, x\2, t=p; forprime(q=2, min(x\t, p-1), listput(v, (t*q)^2))); Set(v) \\ Charles R Greathouse IV, Sep 22 2015 (Magma) [k^2:k in [1..150]| IsSquarefree(k) and #PrimeDivisors(k) eq 2]; // Marius A. Burtea, Oct 24 2019 (Python)
from math import isqrt
from sympy import primepi, primerange
def f(x): return int(n+x+(t:=primepi(s:=isqrt(x)))+(t*(t-1)>>1)-sum(primepi(x//k) for k in primerange(1, s+1)))
m, k = n, f(n)
while m != k:
m, k = k, f(k)
Product of the cube of a prime ( A030078) and a different prime.
+10
41
24, 40, 54, 56, 88, 104, 135, 136, 152, 184, 189, 232, 248, 250, 296, 297, 328, 344, 351, 375, 376, 424, 459, 472, 488, 513, 536, 568, 584, 621, 632, 664, 686, 712, 776, 783, 808, 824, 837, 856, 872, 875, 904, 999, 1016, 1029, 1048, 1096, 1107, 1112
EXAMPLE
a(4)= 56 since 56 = 2*2*2*7.
MATHEMATICA
Select[ Range[1500], Sort[ Transpose[ FactorInteger[ # ]] [[2]]] == {1, 3} & ]
Module[{upto=1200}, Select[(Union[Flatten[{#[[1]]^3 #[[2]], #[[1]]#[[2]]^3}&/@Subsets[Prime[Range[upto/8]], {2}]]]), #<=upto&]] (* Harvey P. Dale, May 23 2015 *)
PROG
(PARI) list(lim)=my(v=List(), t); forprime(p=2, (lim\2)^(1/3), t=p^3; forprime(q=2, lim\t, if(p==q, next); listput(v, t*q))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Jul 20 2011
Product of exactly four primes, three of which are distinct (p^2*q*r).
+10
33
60, 84, 90, 126, 132, 140, 150, 156, 198, 204, 220, 228, 234, 260, 276, 294, 306, 308, 315, 340, 342, 348, 350, 364, 372, 380, 414, 444, 460, 476, 490, 492, 495, 516, 522, 525, 532, 550, 558, 564, 572, 580, 585, 620, 636, 644, 650, 666, 693, 708, 726
EXAMPLE
a(1) = 60 since 60 = 2*2*3*5 and has three distinct prime factors.
MATHEMATICA
pefp[{a_, b_, c_}]:={a^2 b c, a b^2 c, a b c^2}; Module[{upto=800}, Select[ Flatten[ pefp/@Subsets[Prime[Range[PrimePi[upto/6]]], {3}]]//Union, #<= upto&]] (* Harvey P. Dale, Oct 02 2018 *)
PROG
(PARI) list(lim)=my(v=List(), t, x, y, z); forprime(p=2, lim^(1/4), t=lim\p^2; forprime(q=p+1, sqrtint(t), forprime(r=q+1, t\q, x=p^2*q*r; y=p*q^2*r; listput(v, x); if(y<=lim, listput(v, y); z=p*q*r^2; if(z<=lim, listput(v, z)))))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Jul 15 2011
Number of factorizations of n with alternating product < 1.
+10
22
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 2, 1, 1, 0, 4, 0, 1, 1, 2, 0, 3, 0, 3, 1, 1, 1, 3, 0, 1, 1, 4, 0, 3, 0, 2, 2, 1, 0, 6, 0, 2, 1, 2, 0, 4, 1, 4, 1, 1, 0, 6, 0, 1, 2, 3, 1, 3, 0, 2, 1, 3, 0, 8, 0, 1, 2, 2, 1, 3, 0, 6, 1, 1, 0, 6, 1, 1, 1
COMMENTS
All such factorizations have even length and alternating sum < 0, so partitions of this type are counted by A344608. Also the number of factorizations of n with alternating sum < 0.
A factorization of n is a weakly increasing sequence of positive integers > 1 with product n.
We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).
EXAMPLE
The a(n) factorizations for n = 6, 12, 24, 30, 48, 72, 96, 120:
2*3 2*6 3*8 5*6 6*8 8*9 2*48 2*60
3*4 4*6 2*15 2*24 2*36 3*32 3*40
2*12 3*10 3*16 3*24 4*24 4*30
2*2*2*3 4*12 4*18 6*16 5*24
2*2*2*6 6*12 8*12 6*20
2*2*3*4 2*2*2*9 2*2*3*8 8*15
2*2*3*6 2*2*4*6 10*12
2*3*3*4 2*3*4*4 2*2*5*6
2*2*2*12 2*3*4*5
2*2*2*2*2*3 2*2*2*15
2*2*3*10
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1), {i, Length[q]}];
Table[Length[Select[facs[n], altprod[#]<1&]], {n, 100}]
CROSSREFS
Allowing any integer alternating product gives A347437, additive A347446. The equal version (= 1 instead of < 1) is A347438. Allowing any integer reciprocal alternating product gives A347439. The complement (>= 1 instead of < 1) is counted by A347456. A038548 counts possible reverse-alternating products of factorizations.
A046099 counts factorizations with no alternating permutations.
A071321 gives the alternating sum of prime factors (reverse: A071322).
A236913 counts partitions of 2n with reverse-alternating sum <= 0.
A273013 counts ordered factorizations of n^2 with alternating product 1.
A347460 counts possible alternating products of factorizations.
Number of nonsquare divisors of n.
+10
21
0, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 4, 1, 3, 3, 2, 1, 4, 1, 4, 3, 3, 1, 6, 1, 3, 2, 4, 1, 7, 1, 3, 3, 3, 3, 5, 1, 3, 3, 6, 1, 7, 1, 4, 4, 3, 1, 7, 1, 4, 3, 4, 1, 6, 3, 6, 3, 3, 1, 10, 1, 3, 4, 3, 3, 7, 1, 4, 3, 7, 1, 8, 1, 3, 4, 4, 3, 7, 1, 7, 2, 3, 1, 10, 3, 3, 3, 6, 1, 10, 3, 4, 3, 3, 3, 9, 1, 4, 4, 5, 1, 7, 1
FORMULA
Sum_{k=1..n} a(k) ~ n*log(n) + (2*gamma - zeta(2) - 1)*n, where gamma is Euler's constant ( A001620). - Amiram Eldar, Dec 01 2023
EXAMPLE
a(36)=5 because the set of divisors of 36 has tau(36)=nine elements, {1, 2, 3, 4, 6, 9, 12, 18, 36}, five of which, that is {2, 3, 6, 12, 18}, are not perfect squares.
MAPLE
local a, d ;
a := 0 ;
for d in numtheory[divisors](n) do
if not issqr(d) then
a := a+1 ;
end if;
end do:
a;
end proc:
MATHEMATICA
Table[Count[Divisors[n], _?(#!=Floor[Sqrt[#]]^2&)], {n, 110}] (* Harvey P. Dale, Jul 10 2013 *) a[1] = 0; a[n_] := Times @@ (1 + (e = Last /@ FactorInteger[n])) - Times @@ (1 + Floor[e/2]); Array[a, 100] (* Amiram Eldar, Jul 22 2019 *)
PROG
(Haskell)
a056595 n = length [d | d <- [1..n], mod n d == 0, a010052 d == 0]
Search completed in 0.055 seconds
| 
