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
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Étienne Fouvry, Claude Levesque, Michel Waldschmidt, Representation of integers by cyclotomic binary forms, arXiv:1712.09019 [math.NT], 2017.
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)]
println(L) # Peter Luschny, Feb 21 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Lei Zhou, Feb 13 2012
STATUS
approved