A322936 -id:A322936 - cp's OEIS frontend

A323215 Numbers k such that row k of A322936 is not empty and has only primes as members.

5, 8, 9, 10, 12, 18, 24, 30

Offset: 1

Peter Luschny, Apr 01 2019

a is strongly prime to n if and only if a <= n is prime to n and a 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.)
From Robert Israel, Apr 02 2019: (Start)
If there is at least one prime <= sqrt(n) that divides neither n nor n-1, then its square is strongly prime to n and not prime. If there does not exist such a prime, then the first Chebyshev function theta(sqrt(n)) = Sum_{p <= sqrt(n)} log(p) <= 2 log(n). Now it is known that theta(x) = x + O(x/log(x)), so this can't happen if n is sufficiently large. Thus the sequence is finite.
The largest n for which no such p exists appears to be 120. There are none between 121 and 10^7. It is possible that a sufficiently tight lower bound on theta together with a finite search can be used to prove that there are no other terms of the sequence. (End)
There are no more terms.  See proof at A307345. - Robert Israel, Apr 03 2019

Peter Luschny, Strong Coprimality.

Cf. A181830, A141341, A307345, A322936, A322937.

filter:= proc(n) local k, found;
  found:= false;
  for k from 2 to n-2 do
    if igcd(k,n)=1 and (n-1) mod k <> 0 then
      found:= true;
      if not isprime(k) then return false fi;
    fi
  od;
  found
end proc:
select(filter, [$1..1000]); # Robert Israel, Apr 02 2019

Select[Range[10^3], With[{n = #}, AllTrue[Select[Range[2, n], And[GCD[#, n] == 1, Mod[n - 1, #] != 0] &] /. {} -> {0}, PrimeQ]] &] (* Michael De Vlieger, Apr 01 2019 *)

# uses[A322936row from A322936]
def isA323215(n):
    return all(is_prime(p) for p in A322936row(n))
[n for n in (1..100) if isA323215(n)] # Peter Luschny, Apr 03 2019

Name corrected after a notice from Robert Israel by Peter Luschny, Apr 02 2019

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.

Original entry on oeis.org

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

Peter Luschny, Apr 01 2019

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.)

			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}

Peter Luschny, Strong Coprimality

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

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);

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

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))

cp's OEIS Frontend

A323215 Numbers k such that row k of A322936 is not empty and has only primes as members.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Extensions