Displaying 1-10 of 20 results found.
0, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 1, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 1, 1, 1, 1, 37, 1, 1, 1, 41, 1, 43, 1, 1, 1, 47, 1, 7, 1, 1, 1, 53, 1, 1, 1, 1, 1, 59, 1, 61, 1, 1, 2, 1, 1, 67
Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).
(Formerly M0517 N0185)
+10
1059
1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227
COMMENTS
The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.) These numbers are (apart from 1) the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004 Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - Amarnath Murthy, Jan 09 2002 These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - Mats Granvik, Nov 18 2007 These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (= A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - M. F. Hasler, Jan 18 2007, Apr 18 2010 Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - M. F. Hasler, Apr 04 2008 Also, { A138929(k) ; k>1} = {2* A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - M. F. Hasler, Apr 04 2008 Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - Juri-Stepan Gerasimov, Dec 09 2009, Mar 10 2010 The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - W. Edwin Clark, Aug 05 2014 Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - Michel Marcus, Jan 16 2019 Possible numbers of elements in a finite vector space. - Jianing Song, Apr 22 2021
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
FORMULA
Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - N. J. A. Sloane, Oct 31 2014, corrected by M. F. Hasler, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).] m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)= A019434(k) or a(n)= A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - M. F. Hasler, Jan 18 2007, Apr 18 2010
MAPLE
readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d, `, n) fi: od:
# second Maple program:
a:= proc(n) option remember; local k; for k from
1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
MATHEMATICA
Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski *)
PROG
(Magma) [1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by Arkadiusz Wesolowski, Jul 20 2012 (PARI) A000961(n, l=-1, k=0)=until(n--<1, until(l<lcm(l, k++), ); l=lcm(l, k)); k print_ A000961(lim=999, l=-1)=for(k=1, lim, l==lcm(l, k) && next; l=lcm(l, k); print1(k, ", ")) \\ M. F. Hasler, Jan 18 2007 (PARI) nextA000961(n)=my(m, r, p); m=2*n; for(e=1, ceil(log(n+0.01)/log(2)), r=(n+0.01)^(1/e); p=prime(primepi(r)+1); m=min(m, p^e)); m \\ Michael B. Porter, Nov 02 2009 (PARI) list(lim)=my(v=primes(primepi(lim)), u=List([1])); forprime(p=2, sqrtint(lim\1), for(e=2, log(lim+.5)\log(p), listput(u, p^e))); vecsort(concat(v, Vec(u))) \\ Charles R Greathouse IV, Nov 20 2012 (Haskell)
import Data.Set (singleton, deleteFindMin, insert)
a000961 n = a000961_list !! (n-1)
a000961_list = 1 : g (singleton 2) (tail a000040_list) where
g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
where (m, s') = deleteFindMin s
(Sage)
R = [1]
for i in (2..n):
if i.is_prime_power(): R.append(i)
return R
(Python)
from sympy import primerange
def A000961_list(limit): # following Python style, list terms < limit L = [1]
for p in primerange(1, limit):
pe = p
while pe < limit:
L.append(pe)
pe *= p
(Python)
from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x, k)[0]) for k in range(1, x.bit_length())))
m, k = n, f(n)
while m != k:
m, k = k, f(k)
CROSSREFS
There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Largest squarefree number dividing n: the squarefree kernel of n, rad(n), radical of n.
+10
995
1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30, 31, 2, 33, 34, 35, 6, 37, 38, 39, 10, 41, 42, 43, 22, 15, 46, 47, 6, 7, 10, 51, 26, 53, 6, 55, 14, 57, 58, 59, 30, 61, 62, 21, 2, 65, 66, 67, 34, 69, 70, 71, 6, 73, 74, 15, 38, 77, 78
COMMENTS
Multiplicative with a(p^e) = p.
Product of the distinct prime factors of n.
A note on square roots of numbers: we can write sqrt(n) = b*sqrt(c) where c is squarefree. Then b = A000188(n) is the "inner square root" of n, c = A007913(n), lcm(b,c) = A007947(n) = "squarefree kernel" of n and b*c = A019554(n) = "outer square root" of n. The characterization a(n) = lcm(b,c) from the above is incorrect. It fails when n is biquadrateful ( A046101). As an example, when n = 48 then sqrt(48) = 4*sqrt(3), so b = 4 and c = 3; however a(48) = 6 is not lcm(4, 3). - Jeppe Stig Nielsen, Oct 10 2021 Also the least common multiple of the prime factors of n. - Peter Luschny, Mar 22 2011 The Mobius transform of the sequence generates the sequence of absolute values of A097945. - R. J. Mathar, Apr 04 2011 Appears to be the period length of k^n mod n. For example, n^12 mod 12 has period 6, repeating 1,4,9,4,1,0, so a(12)= 6. - Gary Detlefs, Apr 14 2013 a(n) is also the smallest base (also termed radix) for which the representation of 1/n is of finite length. For example a(12) = 6 and 1/12 in base 6 is 0.03, which is of finite length. - Lee A. Newberg, Jul 27 2016 a(n) is also the divisor k of n such that d(k) = 2^omega(n). a(n) is also the smallest divisor u of n such that n divides u^n. - Juri-Stepan Gerasimov, Apr 06 2017
FORMULA
If n = Product_j (p_j^k_j) where p_j are distinct primes, then a(n) = Product_j (p_j).
Dirichlet g.f.: zeta(s)*Product_{primes p} (1+p^(1-s)-p^(-s)). - R. J. Mathar, Jan 21 2012 a(n) = Product_{d|n} d^moebius(n/d) (see Billal link). - Michel Marcus, Jan 06 2015 a(n) = n/( Sum_{k=1..n} (floor(k^n/n)-floor((k^n - 1)/n)) ) = e^(Sum_{k=2..n} (floor(n/k) - floor((n-1)/k))* A010051(k)*M(k)) where M(n) is the Mangoldt function. - Anthony Browne, Jun 17 2016 G.f.: Sum_{k>=1} phi(k)*mu(k)^2*x^k/(1 - x^k). - Ilya Gutkovskiy, Apr 11 2017 Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)). - Vaclav Kotesovec, Dec 18 2019 a(n^2) = a(n).
(End)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2.
a(n) = Sum_{k=1..n} mu(gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)).
For n>1, Sum_{k=1..n} a(gcd(n,k))*mu(a(gcd(n,k)))*phi(gcd(n,k))/gcd(n,k) = 0.
For n>1, Sum_{k=1..n} a(n/gcd(n,k))*mu(a(n/gcd(n,k)))*phi(gcd(n,k))*gcd(n,k) = 0. (End)
EXAMPLE
G.f. = x + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 6*x^6 + 7*x^7 + 2*x^8 + 3*x^9 + ... - Michael Somos, Jul 15 2018
MAPLE
with(numtheory); A007947 := proc(n) local i, t1, t2; t1 := ifactors(n)[2]; t2 := mul(t1[i][1], i=1..nops(t1)); end; A007947 := n -> ilcm(op(numtheory[factorset](n))):
A:= n -> convert(numtheory:-factorset(n), `*`):
seq(NumberTheory:-Radical(n), n = 1..78); # Peter Luschny, Jul 20 2021
MATHEMATICA
rad[n_] := Times @@ (First@# & /@ FactorInteger@ n); Array[rad, 78] (* Robert G. Wilson v, Aug 29 2012 *) Table[Last[Select[Divisors[n], SquareFreeQ]], {n, 100}] (* Harvey P. Dale, Jul 14 2014 *) a[ n_] := If[ n < 1, 0, Sum[ EulerPhi[d] Abs @ MoebiusMu[d], {d, Divisors[ n]}]]; (* Michael Somos, Jul 15 2018 *) Table[Product[p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* Vaclav Kotesovec, May 20 2020 *)
PROG
(PARI) for(n=1, 100, print1(direuler(p=2, n, (1 + p*X - X)/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Jun 14 2020 (Magma) [ &*PrimeDivisors(n): n in [1..100] ]; // Klaus Brockhaus, Dec 04 2008 (Haskell)
(Sage) def A007947(n): return mul(p for p in prime_divisors(n)) (Python)
from sympy import primefactors, prod
def a(n): return 1 if n < 2 else prod(primefactors(n))
CROSSREFS
More general factorization-related properties, specific to n: A020639, A028234, A020500, A010051, A284318, A000005, A001221, A005361, A034444, A014963, A128651, A267116. A003961, A059896 are used to express relationship between terms of this sequence.
Least common multiple (or LCM) of {1, 2, ..., n} for n >= 1, a(0) = 1.
(Formerly M1590)
+10
371
1, 1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240, 232792560, 232792560, 232792560, 232792560, 5354228880, 5354228880, 26771144400, 26771144400, 80313433200, 80313433200, 2329089562800, 2329089562800
COMMENTS
The minimal exponent of the symmetric group S_n, i.e., the least positive integer for which x^a(n)=1 for all x in S_n. - Franz Vrabec, Dec 28 2008 Product over all primes of highest power of prime less than or equal to n. a(0) = 1 by convention.
Also smallest number whose set of divisors contains an n-term arithmetic progression. - Reinhard Zumkeller, Dec 09 2002 An assertion equivalent to the Riemann hypothesis is: | log(a(n)) - n | < sqrt(n) * log(n)^2. - Lekraj Beedassy, Aug 27 2006. (This is wrong for n = 1 and n = 2. Should "for n large enough" be added? - Georgi Guninski, Oct 22 2011) Corollary 3 of Farhi gives a proof that a(n) >= 2^(n-1). - Jonathan Vos Post, Jun 15 2009 Greg Martin (see link) proved that "the product of the Gamma function sampled over the set of all rational numbers in the open interval (0,1) whose denominator in lowest terms is at most n" equals (2*Pi)^(1/2)*a(n)^(-1/2). - Jonathan Vos Post, Jul 28 2009 a(n+1) is the smallest integer such that all polynomials a(n+1)*(1^i + 2^i + ... + m^i) in m, for i=0,1,...,n, are polynomials with integer coefficients. - Vladimir Shevelev, Dec 23 2011 For n > 2, (n-1) = Sum_{k=2..n} exp(a(n)*2*i*Pi/k). - Eric Desbiaux, Sep 13 2012 For n > 0, a(n) is the smallest number k such that n is the n-th divisor of k. - Michel Lagneau, Apr 24 2014 Slowest growing integer > 0 in Z converging to 0 in Z^ when considered as profinite integer. - Herbert Eberle, May 01 2016 What is the largest number of consecutive terms that are all equal? I found 112 equal terms from a(370261) to a(370372). - Dmitry Kamenetsky, May 05 2019 Answer: there exist arbitrarily long sequences of consecutive terms with the same value; also, the maximal run of consecutive terms with different values is 5 from a(1) to a(5) (see link Roger B. Eggleton). - Bernard Schott, Aug 07 2019 Related to the inequality (54) in Ramanujan's paper about highly composite numbers A002182, also used in A199337: a( A329570(m))^2 is a (not minimal) bound above which all highly composite numbers are divisible by m, according to the right part of that inequality. - M. F. Hasler, Jan 04 2020 For n > 2, a(n) is of the form 2^e_1 * p_2^e_2 * ... * p_m^e_m, where e_m = 1 and e = floor(log_2(p_m)) <= e_1. Therefore, 2^e * p_m^e_m is a primitive Zumkeler number ( A180332). Therefore, 2^e_1 * p_m^e_m is a Zumkeller number ( A083207). Therefore, for n > 2, a(n) = 2^e_1 * p_m^e_m * r, where r is relatively prime to 2*p_m, is a Zumkeller number (see my proof at A002182 for details). - Ivan N. Ianakiev, May 10 2020 For n > 1, 2|(a(n)+2) ... n|(a(n)+n), so a(n)+2 .. a(n)+n are all composite and (part of) a prime gap of at least n. (Compare n!+2 .. n!+n). - Stephen E. Witham, Oct 09 2021
REFERENCES
J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 365.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
R. E. Crandall and C. Pomerance, Prime numbers: a computational perspective, MR2156291, p. 61. S. Ramanujan, Highly composite numbers, Proceedings of the London Mathematical Society ser. 2, vol. XIV, no. 1 (1915), pp 347-409. (A variant of a better quality with an additional footnote is available here.)
FORMULA
The prime number theorem implies that lcm(1,2,...,n) = exp(n(1+o(1))) as n -> infinity. In other words, log(lcm(1,2,...,n))/n -> 1 as n -> infinity. - Jonathan Sondow, Jan 17 2005 a(n) = Product (p^(floor(log n/log p))), where p runs through primes not exceeding n (i.e., primes 2 through A007917(n)). - Lekraj Beedassy, Jul 27 2004 Greg Martin showed that a(n) = lcm(1,2,3,...,n) = Product_{i = Farey(n), 0 < i < 1} 2*Pi/Gamma(i)^2. This can be rewritten (for n > 1) as a(n) = (1/2)*(Product_{i = Farey(n), 0 < i <= 1/2} 2*sin(i*Pi))^2. - Peter Luschny, Aug 08 2009 Recursive formula useful for computations: a(0)=1; a(1)=1; a(n)=lcm(n,a(n-1)). - Enrique Pérez Herrero, Jan 08 2011 if n is a prime power p^k then a(n)=a(p^k)=p*a(n-1), otherwise a(n)=a(n-1).
a(n) = Product_{k=2..n} (1 + ( A007947(k)-1)*floor(1/ A001221(k))), for n > 1. (End) a(n) = exp(Sum_{k=1..n} Sum_{d|k} moebius(d)*log(k/d)). - Peter Luschny, Sep 01 2012 a(n) = exp(Psi(n)) = 2 * Product_{k=2.. A002088(n)} (1 - exp(2*Pi*i * A038566(k+1) / A038567(k))), where i is the imaginary unit, and Psi the second Chebyshev's function. - Eric Desbiaux, Aug 13 2014 Nair (1982) proved that 2^n <= a(n) <= 4^n for n >= 9. See also Farhi (2009). Nair also proved that
a(n) = lcm(m*binomial(n,m): 1 <= m <= n) and
a(n) = gcd(a(m)*binomial(n,m): n/2 <= m <= n). (End)
EXAMPLE
LCM of {1,2,3,4,5,6} = 60. The primes up to 6 are 2, 3 and 5. floor(log(6)/log(2)) = 2 so the exponent of 2 is 2.
floor(log(6)/log(3)) = 1 so the exponent of 3 is 1.
floor(log(6)/log(5)) = 1 so the exponent of 5 is 1. Therefore, a(6) = 2^2 * 3^1 * 5^1 = 60. - David A. Corneth, Jun 02 2017
MAPLE
A003418 := n-> lcm(seq(i, i=1..n));
HalfFarey := proc(n) local a, b, c, d, k, s; a := 0; b := 1; c := 1; d := n; s := NULL; do k := iquo(n + b, d); a, b, c, d := c, d, k*c - a, k*d - b; if 2*a > b then break fi; s := s, (a/b); od: [s] end: LCM := proc(n) local i; (1/2)*mul(2*sin(Pi*i), i=HalfFarey(n))^2 end: # Peter Luschny# next Maple program:
a:= proc(n) option remember; `if`(n=0, 1, ilcm(n, a(n-1))) end:
MATHEMATICA
FoldList[ LCM, 1, Range@ 28]
Table[Product[Prime[i]^Floor[Log[Prime[i], n]], {i, PrimePi[n]}], {n, 0, 28}] (* Wei Zhou, Jun 25 2011 *) Table[Product[Cyclotomic[n, 1], {n, 2, m}], {m, 0, 28}] (* Fred Daniel Kline, May 22 2014 *) a1[n_] := 1/12 (Pi^2+3(-1)^n (PolyGamma[1, 1+n/2] - PolyGamma[1, (1+n)/2])) // Simplify
a[n_] := Denominator[Sqrt[a1[n]]];
PROG
(PARI) a(n)=local(t); t=n>=0; forprime(p=2, n, t*=p^(log(n)\log(p))); t
(PARI) a(n)=if(n<1, n==0, 1/content(vector(n, k, 1/k)))
(PARI) a(n)=my(v=primes(primepi(n)), k=sqrtint(n), L=log(n+.5)); prod(i=1, #v, if(v[i]>k, v[i], v[i]^(L\log(v[i])))) \\ Charles R Greathouse IV, Dec 21 2011 (PARI) n=1; lim=100; i=1; j=1; until(n==lim, a=lcm(j, i+1); i++; j=a; n++; print(n" "a); ); \\ Mike Winkler, Sep 07 2013 (Sage) [lcm(range(1, n)) for n in range(1, 30)] # Zerinvary Lajos, Jun 06 2009 (Haskell)
a003418 = foldl lcm 1 . enumFromTo 2
(Scheme) (define ( A003418 n) (let loop ((n n) (m 1)) (if (zero? n) m (loop (- n 1) (lcm m n))))) ;; Antti Karttunen, Jan 03 2018 (Python)
from functools import reduce
from operator import mul
from sympy import sieve
def integerlog(n, b): # find largest integer k>=0 such that b^k <= n
kmin, kmax = 0, 1
while b**kmax <= n:
kmax *= 2
while True:
kmid = (kmax+kmin)//2
if b**kmid > n:
kmax = kmid
else:
kmin = kmid
if kmax-kmin <= 1:
break
return kmin
return reduce(mul, (p**integerlog(n, p) for p in sieve.primerange(1, n+1)), 1) # Chai Wah Wu, Mar 13 2021 (Python) # generates initial segment of sequence
from math import gcd
from itertools import accumulate
def lcm(a, b): return a * b // gcd(a, b)
def aupton(nn): return [1] + list(accumulate(range(1, nn+1), lcm))
CROSSREFS
Cf. A000142, A000793, A002110, A002182, A002201, A002944, A014963, A020500, A025527, A038610, A051173, A064446, A064859, A069513, A072938, A093880, A094348, A096179, A099996, A102910, A106037, A119682, A179661, A193181, A225558, A225630, A225632, A225640, A225642. Cf. A025528 (number of prime factors of a(n) with multiplicity). Cf. A275120 (lengths of runs of consecutive equal terms), A276781 (ordinal transform from term a(1)=1 onward).
AUTHOR
Roland Anderson (roland.anderson(AT)swipnet.se)
Numbers that are not powers of primes p^k (k >= 0); complement of A000961.
+10
194
6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112
COMMENTS
The sequence of numbers divisible by a prime number of primes coincides with this up to 210, which has 4 prime factors. - Lior Manor Aug 23 2001 Numbers n such that LCM of proper divisors of n equals neither 1 nor n. - Labos Elemer, Dec 01 2004 a(n) provides bases b in which automorphic numbers m^2 ending with m in base b exist. In the complement there aren't any automorphic numbers. - Martin Renner, Dec 07 2011 Numbers with at least 2 distinct prime factors. - Jonathan Sondow, Oct 17 2013 There exists an equiangular n-gon whose edge lengths form a permutation of 1, 2, ..., n if and only if n is in the sequence (see Woeginger's survey and Munteanu & Munteanu). - Jonathan Sondow, Oct 17 2013 Numbers that are the product of two relatively prime factors. These numbers are used in testing a sequence for multiplicativity. - Michael Somos, Jun 02 2015 A theorem from Donald McCarthy: Let d be any positive integer which is not a prime power; then there exists a finite group whose order is divisible by d but which contains no subgroup of order d (see link and A340511). - Bernard Schott, Dec 04 2021
MAPLE
a := proc(n) numtheory[factorset](n); if 1 < nops(%) then n else NULL fi end:
PROG
(Magma) IsA024619:=func< n | not IsPrime(n) and not (t and IsPrime(b) where t, b, _:=IsPower(n)) >; [ n: n in [2..200] | IsA024619(n) ]; // Klaus Brockhaus, Feb 25 2011 (Haskell)
a024619 n = a024619_list !! (n-1)
a024619_list = filter ((== 0) . a010055) [1..]
(Sage)
return [k for k in (2..n) if not k.is_prime() and not k.is_prime_power()]
(Python)
from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def f(x): return int(n+1+sum(primepi(integer_nthroot(x, k)[0]) for k in range(1, x.bit_length())))
m, k = n, f(n)
while m != k:
m, k = k, f(k)
Exponential of Mangoldt function M(n): a(n) = 1 unless n is a prime or prime power, in which case a(n) = that prime.
+10
128
1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 1, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 1, 1, 1, 1, 37, 1, 1, 1, 41, 1, 43, 1, 1, 1, 47, 1, 7, 1, 1, 1, 53, 1, 1, 1, 1, 1, 59, 1, 61, 1, 1, 2, 1, 1, 67, 1, 1, 1, 71, 1, 73, 1, 1, 1, 1, 1, 79, 1, 3, 1, 83, 1, 1, 1, 1, 1, 89, 1, 1, 1, 1, 1, 1
COMMENTS
There are arbitrarily long runs of ones (Sierpiński). - Franz Vrabec, Sep 26 2005 a(n) is the smallest positive integer such that n divides Product_{k=1..n} a(k), for all positive integers n. - Leroy Quet, May 01 2007 For n>1, resultant of the n-th cyclotomic polynomial with the 1st cyclotomic polynomial x-1. - Ralf Stephan, Aug 14 2013 A368749(n) is the smallest prime p such that the interval [a(p), a(q)] contains n 1's; q = nextprime(p), n >= 0. - David James Sycamore, Mar 21 2024
REFERENCES
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Section 17.7.
I. Vardi, Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 146-147, 152-153 and 249, 1991.
FORMULA
a(n) = A003418(n) / A003418(n-1) = lcm {1..n} / lcm {1..n-1}. [This is equivalent to saying that this sequence is the LCM-transform (as defined by Nowicki, 2013) of the positive integers. - David James Sycamore, Jan 09 2024.] a(n) = 1/Product_{d|n} d^mu(d) = Product_{d|n} (n/d)^mu(d). - Vladeta Jovovic, Jan 24 2002 a(n) = gcd( C(n+1,1), C(n+2,2), ..., C(2n,n) ) where C(n,k) = binomial(n,k). - Benoit Cloitre, Jan 31 2003 a(n) = gcd(C(n,1), C(n+1,2), C(n+2,3), ...., C(2n-2,n-1)), where C(n,k) = binomial(n,k). - Benoit Cloitre, Jan 31 2003; corrected by Ant King, Dec 27 2005 Note: a(n) != gcd( A008472(n), A007947(n)) = A099636(n), GCD of rad(n) and sopf(n) (this fails for the first time at n=30), since a(30) = 1 but gcd(rad(30), sopf(30)) = gcd(30,10) = 10. a(n) = Product_{k=1..n-1, if(gcd(n, k)=1, 1-exp(2*Pi*i*k/n), 1)}, i=sqrt(-1); a(n) = n/ A048671(n). - Paul Barry, Apr 15 2005 Sum_{n>=1} (log(a(n))-1)/n = -2* A001620 [Bateman Manuscript Project Vol III, ed. by Erdelyi et al.]. - R. J. Mathar, Mar 09 2008 a(n) = (2*Pi)^phi(n) / Product_{gcd(n,k)=1} Gamma(k/n)^2 (for n > 1). - Peter Luschny, Aug 08 2009 a(n) = Product_{k=1..n-1} if(gcd(k,n)=1, 2*sin(Pi*k/n), 1). - Peter Luschny, Jun 09 2011 Dirichlet g.f.: Sum_{n>0} e^Lambda(n)/n^s = Zeta(s) + Sum_{p prime} Sum_{k>0} (p-1)/p^(k*s) = Zeta(s) - ppzeta(s) + Sum(p prime, p/(p^s-1)); for a ppzeta definition see A010055. - Enrique Pérez Herrero, Jan 19 2013 a(n) = exp(lim_{x->1} zeta(s)*Sum_{d|n} moebius(d)/d^(s-1)) for n>1. - Mats Granvik, Jul 31 2013 a(n) = 1 + Sum_{k=2..n} (k-1)* A010051(k)*(floor(k^n/n) - floor((k^n - 1)/n)). - Anthony Browne, Jun 16 2016 The Dirichlet series for log(a(n)) = Lambda(n) is given by the logarithmic derivative of the zeta function -zeta'(s)/zeta(s). - Mats Granvik, Oct 30 2016
MAPLE
a := n -> if n < 2 then 1 else numtheory[factorset](n); if 1 < nops(%) then 1 else op(%) fi fi; # Peter Luschny, Jun 23 2009 A014963 := n -> n/ilcm(op(numtheory[divisors](n) minus {1, n}));
LCMXFM:=proc(a) local p, q, b, i, k, n:
if whattype(a) <> list then RETURN([]); fi:
n:=nops(a):
b:=[a[1]]: p:=[a[1]];
for i from 2 to n do q:=[op(p), a[i]]; k := lcm(op(q))/lcm(op(p));
b:=[op(b), k]; p:=q;; od:
RETURN(b);
end:
MATHEMATICA
a[n_?PrimeQ] := n; a[n_/; Length[FactorInteger[n]] == 1] := FactorInteger[n][[1]][[1]]; a[n_] := 1; Table[a[n], {n, 95}] (* Alonso del Arte, Jan 16 2011 *)
PROG
(PARI)
{
local(r);
if( isprime(n), return(n));
if( ispower(n, , &r) && isprime(r), return(r) );
return(1);
(Haskell)
a014963 1 = 1
a014963 n | until ((> 0) . (`mod` spf)) (`div` spf) n == 1 = spf
| otherwise = 1
where spf = a020639 n
(Sage)
def A014963(n) : return simplify(exp(add(moebius(d)*log(n/d) for d in divisors(n)))) (Sage)
def a(n):
if n == 1: return 1
return prod(1 - E(n)**k for k in ZZ(n).coprime_integers(n+1))
[a(n) for n in range(1, 14)] # F. Chapoton, Mar 17 2020 (Python)
from sympy import factorint
y = factorint(n)
return list(y.keys())[0] if len(y) == 1 else 1
CROSSREFS
Apart from initial 1, same as A020500. With ones replaced by zeros, equal to A120007. Cf. A003418, A007947, A008683, A008472, A008578, A048671 (= n/a(n)), A072107 (partial sums), A081386, A081387, A099636, A100994, A100995, A140255 (inverse Mobius transform), A140254 (Mobius transform), A297108, A297109, A340675.
Irregular triangle read by rows: coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order).
+10
35
0, 1, -1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 0, 1, -1, 1, 0, -1, 1
COMMENTS
We follow Maple in defining Phi_0 to be x; it could equally well be taken to be 1.
The length of row n >= 1 of this table is phi(n) + 1 = A000010(n) + 1. Row n = 0 has here length 2. Phi_n(x) is the minimal polynomial of omega_n := exp(i*2*Pi/n) over the rationals. Namely, Phi_n(x) = Product_{k=0..n-1, gcd(k,n)=1} (x - (omega_n)^k). See the Graham et al. reference, 4.50 a, pp. 149, 506.
Phi_n(x) = Product_{d|n} (x^d - 1)^(mu(n/d)) with the Moebius function mu(n) = A008683(n), n >= 1. See the Graham et al. reference, 4.50 b, pp. 149, 506. Phi_n(x) = Phi_{rad(n)}(x^(n/rad(n))), n >= 2, with rad(n) = A007947(n), the squarefree kernel of n. Proof from the preceding formula, where only squarefree n/d ( A005117) from the set of divisors of n enter, by mapping each factor (numerator or denominator) of the left hand side to one of the right hand side and vice versa. (End)
Each row can be considered as the last column of the companion matrix of the cyclotomic polynomial: A000010(n) is the size of such a square matrix, last column has opposite signs and the last term (before last term of each row in A013595) equal to A008683(n). - Eric Desbiaux, Dec 14 2015
REFERENCES
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968; see p. 90.
Z. I. Borevich and I. R. Shafarevich, Number Theory. Academic Press, NY, 1966, p. 325.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1991, p. 137.
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194.
EXAMPLE
Phi_0 = x; Phi_1 = x - 1; Phi_2 = x + 1; Phi_3 = x^2 + x + 1; Phi_4 = x^2 + 1; ...
The irregular triangle a(n,m) begins:
n\m 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
0: 0 1
1: -1 1
2: 1 1
3: 1 1 1
4: 1 0 1
5: 1 1 1 1 1
6: 1 -1 1
7: 1 1 1 1 1 1 1
8: 1 0 0 0 1
9: 1 0 0 1 0 0 1
10: 1 -1 1 -1 1
11: 1 1 1 1 1 1 1 1 1 1 1
12: 1 0 -1 0 1
13: 1 1 1 1 1 1 1 1 1 1 1 1 1
14: 1 -1 1 -1 1 -1 1
15: 1 -1 0 1 -1 1 0 -1 1
...
Phi_15(x) = (x^1 - 1)*((x^3 - 1)^(-1))*((x^5 - 1)^(-1))*(x^15 - 1) because mu(15) = mu(1) = +1 and mu(3) = mu(5) = -1. Hence Phi_15(x) = 1 - x + x^3 - x^4 + x^5 - x^7 + x^8, giving row n = 15.
Example for the reduction via the squarefree kernel: Phi_12(x) = Phi_6(x^(12/6)) = Phi_6(x^2). By the formula with the Mobius function Phi_6(x) = Phi_2(x^3)/Phi_2(x) = 1 - x + x^2 and with x -> x^2 this becomes Phi_12(x) = 1 - x^2 + x^4.
(End)
MAPLE
N:= 100: # to get coefficients up to cyclotomic(N, x)
with(numtheory):
for n from 0 to N do
C:= cyclotomic(n, x);
L[n]:= seq(coeff(C, x, i), i=0..degree(C));
od:
A:= [seq](L[n], n=0..N): # note that A013595(n) = A[n+1]
MATHEMATICA
Table[CoefficientList[x^KroneckerDelta[n] Cyclotomic[n, x], x], {n, 0, 15}] // Flatten (* Peter Luschny, Dec 27 2016 *)
PROG
(PARI) row(n) = if (n==0, p=x, p = polcyclo(n)); Vecrev(p); \\ Michel Marcus, Dec 14 2015
a(1) = 1; for n > 1, a(n) = prime root of n-th prime power ( A000961).
+10
29
1, 2, 3, 2, 5, 7, 2, 3, 11, 13, 2, 17, 19, 23, 5, 3, 29, 31, 2, 37, 41, 43, 47, 7, 53, 59, 61, 2, 67, 71, 73, 79, 3, 83, 89, 97, 101, 103, 107, 109, 113, 11, 5, 127, 2, 131, 137, 139, 149, 151, 157, 163, 167, 13, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239
COMMENTS
This sequence is related to the cyclotomic sequences A013595 and A020500, leading to the procedure used in the Mathematica program. - Roger L. Bagula, Jul 08 2008 "LCM numeral system": a(n+1) is radix for index n, n >= 0; a(-n+1) is 1/radix for index n, n < 0. - Daniel Forgues, May 03 2014
REFERENCES
Paul J. McCarthy, Algebraic Extensions of Fields, Dover books, 1976, pages 40, 69
MAPLE
cvm := proc(n, level) local f, opf; if n < 2 then RETURN() fi;
f := ifactors(n); opf := op(1, op(2, f)); if nops(op(2, f)) > 1 or
op(2, opf) <= level then RETURN() fi; op(1, opf) end:
A025473_list := n -> [1, seq(cvm(i, 0), i=1..n)];
MATHEMATICA
a = Join[{1}, Flatten[Table[If[PrimeQ[Apply[Plus, CoefficientList[Cyclotomic[n, x], x]]], Apply[Plus, CoefficientList[Cyclotomic[n, x], x]], {}], {n, 1, 1000}]]] (* Roger L. Bagula, Jul 08 2008 *) Join[{1}, First@ First@# & /@ FactorInteger@ Select[Range@ 240, PrimePowerQ]] (* Robert G. Wilson v, Aug 17 2017 *)
PROG
(Sage)
R = [1]
for i in (2..n) :
if i.is_prime_power() :
R.append(prime_divisors(i)[0])
return R
(Haskell)
(Python)
from sympy import primepi, integer_nthroot, primefactors
if n == 1: return 1
def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x, k)[0]) for k in range(1, x.bit_length())))
m, k = n, f(n)
while m != k:
m, k = k, f(k)
2, 4, 6, 8, 10, 14, 16, 18, 22, 26, 32, 34, 38, 46, 50, 54, 58, 62, 64, 74, 82, 86, 94, 98, 106, 118, 122, 128, 134, 142, 146, 158, 162, 166, 178, 194, 202, 206, 214, 218, 226, 242, 250, 254, 256, 262, 274, 278, 298, 302, 314, 326, 334, 338, 346, 358, 362, 382
COMMENTS
Except for the initial term a(1)=2, indices k such that A020513(k)=Phi[k](-1) is prime, where Phi is a cyclotomic polynomial. This is illustrated by the PARI code, although it is probably more efficient to calculate a(n) as 2* A000961(n). { a(n)/2 ; n>1 } are also the indices for which A020500(k)=Phi[k](1) is prime.
FORMULA
Equals {2} union { k | Phi[k](-1)= A020513(k) is prime } = {2} union { 2k | Phi[k](1)= A020500(k) is prime }.
MAPLE
a := n -> `if`(1>=nops(numtheory[factorset](n)), 2*n, NULL):
MATHEMATICA
Join[{2}, Select[ Range[3, 1000], PrimeQ[ Cyclotomic[#, -1]] &]] (* Robert G. Wilson v, Mar 25 2012 - modified by Paolo Xausa, Aug 30 2024 to include a(1) *) 2*Join[{1}, Select[Range[500], PrimePowerQ]] (* Paolo Xausa, Aug 30 2024 *)
PROG
(PARI) print1(2); for( i=1, 999, isprime( polcyclo(i, -1)) & print1(", ", i)) /* use ...subst(polcyclo(i), x, -2)... in PARI < 2.4.2. It should be more efficient to calculate a(n) as 2* A000961(n) ! */ (Python)
from sympy import primepi, integer_nthroot
def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x, k)[0]) for k in range(1, x.bit_length())))
kmin, kmax = 0, 1
while f(kmax) > kmax:
kmax <<= 1
while kmax-kmin > 1:
kmid = kmax+kmin>>1
if f(kmid) <= kmid:
kmax = kmid
else:
kmin = kmid
Cyclotomic polynomials at x=8.
+10
6
8, 7, 9, 73, 65, 4681, 57, 299593, 4097, 262657, 3641, 1227133513, 4033, 78536544841, 233017, 14709241, 16777217, 321685687669321, 261633, 20587884010836553, 16519105, 60247241209, 954437177, 84327972908386521673, 16773121, 1152956690052710401, 61083979321
MAPLE
with(numtheory, cyclotomic); f := n->subs(x=8, cyclotomic(n, x)); seq(f(i), i=0..64);
MATHEMATICA
Join[{8}, Cyclotomic[Range[50], 8]] (* Paolo Xausa, Feb 26 2024 *)
PROG
(Python)
from sympy.polys.specialpolys import cyclotomic_poly
def a(n): return 8 if n == 0 else cyclotomic_poly(n, x=8)
(PARI) a(n) = if (n==0, 8, polcyclo(n, 8)); \\ Michel Marcus, Aug 07 2021
Search completed in 0.021 seconds
|