|
| |
|
|
A206864
|
|
Prime numbers of the form Phi_k(m), where k > 2, |m| > 1, and Phi_k(m) is the k-th cyclotomic polynomial evaluated at m.
|
|
5
|
|
|
|
3, 5, 7, 11, 13, 17, 31, 37, 43, 61, 73, 101, 127, 151, 157, 197, 211, 241, 257, 307, 331, 401, 421, 463, 521, 547, 577, 601, 677, 683, 757, 1093, 1123, 1297, 1483, 1601, 1723, 2551, 2731, 2801, 2917, 2971, 3137, 3307, 3541, 3907, 4357, 4423, 4561, 4831, 5113
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
These are the prime numbers picked from sequence A206942.
Choosing negative m does not generate more primes, so it does not need negative m part in the Mathematica program.
The provided mathematica program generate this sequence in six steps:
Step 1: Find the minimum m such that Phi(6, m) is greater than the search boundary maxdata, and adjust the search boundary to the next: ( maxdata = 5200; max = Ceiling[(1 + Sqrt[1 + 4*(maxdata - 1)])/2]; )
Step 2: Find the even number eulerbound such that 2^(eulerbound+1)-1 > maxdata: ( eulerbound = 2*Floor[(Log[2, maxdata])/2 + 0.5]; )
This is the maximum possible value of Phi(k, 2) when Phi(k, m) has a totient function value of eulerbound;
Step 3: Adjust (up) the eulerbound such that it is an element of A002202 and find the group of ks such that Phi(k, m) has the same totient function value eulerbound: ( phiinv[n_, pl_] := Module[{i, p, e, pe, val}, If[pl == {}, Return[If[n == 1, {1}, {}]]]; val = {}; p = Last[pl]; For[e = 0; pe = 1, e == 0 || Mod[n, (p - 1) pe/p] == 0, e++; pe *= p, val = Join[val, pe*phiinv[If[e == 0, n, n*p/pe/(p - 1)], Drop[pl, -1]]]]; Sort[val]]; phiinv[n_] := phiinv[n, Select[1 + Divisors[n], PrimeQ]]; While[eulergroup = phiinv[eulerbound]; lu = Length[eulergroup]; lu == 0, eulerbound = eulerbound + 2]; )
Step 4: Make list of k values such that the totient function of Phi(k, m) smaller or equal to the chosen Euler boundary eulerbound, and sort it in the order of the Phi(k, 2): ( Select[Range[eulergroup[[Length[eulergroup]]]], EulerPhi[#] <= eulerbound &]; ap = SortBy[t, Cyclotomic[#, 2] &])
Step 5: Scan k in the set of ap, 1 < m <= max, for all appeared primes that are smaller than maxdata: (a = {}; Do[i = 2; While[i++; cc = Cyclotomic[ap[[i]], m]; cc <= maxdata, If[PrimeQ[cc], a = Append[a, cc]]], {m, 2, max}];)
Step 6: Remove duplicate and sort the set generated in the above step: ( Sort[DeleteDuplicates[a]] )
Through these steps, a mathematically abundant algorithm is presented to find all the terms up to an arbitrary bound, without requiring the user to determine any other search parameters.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Prime 3 = Phi_6(2); so a(1) = 3;
Prime 5 = Phi_4(2), so a(2) = 5;
...
Prime 17 = Phi_8(2), so a(6)=17;
Primes 19 and 23 are not in A206942;
Prime 31 = Phi_5(2), so a(7)=31.
|
|
|
MATHEMATICA
|
maxdata = 5200; max = Ceiling[(1 + Sqrt[1 + 4*(maxdata - 1)])/2]; eulerbound = 2*Floor[(Log[2, maxdata])/2 + 0.5]; phiinv[n_, pl_] := Module[{i, p, e, pe, val}, If[pl == {}, Return[If[n == 1, {1}, {}]]]; val = {}; p = Last[pl]; For[e = 0; pe = 1, e == 0 || Mod[n, (p - 1) pe/p] == 0, e++; pe *= p, val = Join[val, pe*phiinv[If[e == 0, n, n*p/pe/(p - 1)], Drop[pl, -1]]]]; Sort[val]]; phiinv[n_] := phiinv[n, Select[1 + Divisors[n], PrimeQ]]; While[eulergroup = phiinv[eulerbound]; lu = Length[eulergroup]; lu == 0, eulerbound = eulerbound + 2]; t = Select[Range[eulergroup[[Length[eulergroup]]]], EulerPhi[#] <= eulerbound &]; ap = SortBy[t, Cyclotomic[#, 2] &]; a = {}; Do[i = 2; While[i++; cc = Cyclotomic[ap[[i]], m]; cc <= maxdata, If[PrimeQ[cc], a = Append[a, cc]]], {m, 2, max}]; Sort[DeleteDuplicates[a]]
(* Alternatively: *)
isA206864[n_] := If[! PrimeQ[n], Return[False],
K = Floor[5.383 Log[n]^1.161]; M = Floor[2 Sqrt[n/3]];
For[k = 3, k <= K, k++, For[x = 2, x <= M, x++,
If[n == Cyclotomic[k, x], Return[True]]]];
Return[False]
]; Select[Range[1000], isA206864] (* Peter Luschny, Feb 21 2018 *)
|
|
|
PROG
|
(Julia)
# Function isA206942 is defined in A206942.
L = [n for n in 1:5113 if isprime(ZZ(n)) && isA206942(n)]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
