A322937 Triangular array in which the n-th row lists the primes strongly prime to n (in ascending order). For the empty rows n = 1, 2, 3, 4 and 6 we set by convention 0.

0, 0, 0, 0, 3, 0, 5, 3, 5, 5, 7, 7, 3, 7, 5, 7, 5, 7, 11, 3, 5, 11, 11, 13, 7, 11, 13, 3, 5, 7, 11, 13, 5, 7, 11, 13, 5, 7, 11, 13, 17, 3, 7, 11, 13, 17, 11, 13, 17, 19, 5, 13, 17, 19, 3, 5, 7, 13, 17, 19, 5, 7, 11, 13, 17, 19, 7, 11, 13, 17, 19, 23

Offset: 1

Author

Peter Luschny, Apr 01 2019

Keywords

• nonn
• tabf

Comments

A number k is strongly prime to n if and only if k <= n is prime to n and k does not divide n-1. See the link to 'Strong Coprimality'. (Our terminology follows the plea of Knuth, Graham and Patashnik in Concrete Mathematics, p. 115.)

Examples

			The length of row n is A181834(n). The triangular array starts:
[1] {}
[2] {}
[3] {}
[4] {}
[5] {3}
[6] {}
[7] {5}
[8] {3, 5}
[9] {5, 7}
[10] {7}
[11] {3, 7}
[12] {5, 7}
[13] {5, 7, 11}
[14] {3, 5, 11}
[15] {11, 13}
[16] {7, 11, 13}
[17] {3, 5, 7, 11, 13}
[18] {5, 7, 11, 13}
[19] {5, 7, 11, 13, 17}
[20] {3, 7, 11, 13, 17}
		

Links

• Peter Luschny, Strong Coprimality

Crossrefs

Cf. A000010, A038566, A181831, A181832, A181833, A181834, A181835, A181836, A322936.

Programs

Maple

Primes := n -> select(isprime, {$1..n}):
StrongCoprimes := n -> select(k->igcd(k, n)=1, {$1..n}) minus numtheory:-divisors(n-1):
StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A322937row := proc(n) if n in {1, 2, 3, 4, 6} then return 0 else op(StrongCoprimePrimes(n)) fi end:
seq(A322937row(n), n=1..25);

Mathematica

Table[Select[Prime@ Range@ PrimePi@ n, And[GCD[#, n] == 1, Mod[n - 1, #] != 0] &] /. {} -> {0}, {n, 25}] // Flatten (* Michael De Vlieger, Apr 01 2019 *)

Sage

def primes_primeto(n):
    return [p for p in prime_range(n) if gcd(p, n) == 1]
def primes_strongly_primeto(n):
    return [p for p in set(primes_primeto(n)) - set((n-1).divisors())]
def A322937row(n):
    if n in [1, 2, 3, 4, 6]: return [0]
    return sorted(primes_strongly_primeto(n))
for n in (1..25): print(A322937row(n))