This site is supported by donations to The OEIS Foundation.

Strong coprimality and strong coprime primes

KEYWORDS: divisorial, coprimorial, strong coprimorial, strong coprime primes, strong coprimality triangle, divisors, common divisors, safe primes, supersafe primes, tau, phi, sigma.

Concerned with sequences: A181832, A181830, A181831, A181834, A181835, A181836, A181837, A181833, A181838, A059957, A007955, A001783, A001221, A005385, A000010, A000005.

The divisorial and the coprimorial

The coprimorial A001783 can be written as

$\prod _{\stackrel {1\leq k\leq n}{k\perp n}}k$ I prefer the name coprimorial´ to phitorial´. Similarly the divisorial A007955 is defined as

$\prod _{\stackrel {1\leq k\leq n}{k\mid n}}k$ Now, what is the ratio coprimorial / divisorial ? It turns out that we have to compare the coprimorial of n with the divisorial of n − 1 to get integer values. Then we can define

${\frac {\prod _{\stackrel {1\leq k\leq n}{k\perp n}}k}{\prod _{\stackrel {1\leq k For n ≥ 0 this sequence starts
1, 1, 1, 1, 1, 3, 1, 20, 15, 35, 7, 36288, 35, 277200, 1485, 4576, 9009, 20432412000, 5005, 1097800704000, 459459, 5912192, 2834325, 2322315553259520000, 1616615

Surprisingly this sequence was not yet in the database.

Definitions

Let a and b be integers.

• a divides b (a | b´)
iff a is in the set of the divisors of b.
• a is prime to b (a ⊥ b´)
iff the set of common positive divisors of a and b is {1}.
• a is strongly prime to b (a ${\underline {\perp }}$ b´)
iff a is prime to b and a does not divide b − 1.

We also suggest to write m ${\underline {\perp }}$ n for m strongly prime to n´ using the Unicode character U+234A (or with TeX \underline{\perp}) extending the proposal to write m ⊥ n for m prime to n´.

Our terminology follows the plea of Knuth, Graham and Patashnik in Concrete Mathematics, p.115.

 Hear us, O mathematicians of the world! Let us not wait any longer! We can make many formulas clearer by defining a new notation now! Let us agree to write m ⊥ n, and to say "m is prime to n", if m and n are relatively prime.

Recall that a strong reason for this notation comes from the fact that

${m\perp n}\iff m_{p}\;n_{p}=0\ {\text{for all }}p.$ mp is the exponent of the prime p in the prime factorization of m. Thus the dot product is zero, like orthogonal vectors (CM, (4.29)).

Using this terminology we can also write (p here always denotes a prime)

${m\ {\underline {\perp }}\ n}\iff {\begin{cases}m_{p}\;n_{p}=0&\forall \;p\;;\\m_{p}\;>(n-1)_{p}&\exists \;p\;.\end{cases}}$ The concept of strong coprimality seems to be new. If I am wrong and you know a reference to an earlier mention please give me a notice.

$A181830(n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}1$ $A181831(n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}k$ $A181832(n)=\prod _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}k$ Let us fix some notation. Euler's φ(n) is the number of k prime to n and Φ(n), the number of k strongly prime to n, is the strong totient of n. The number of positive integers less than or equal to n that are not strongly prime to n is n - Φ(n), the strong cototient of n. For the number of divisors we will write τ(n).

$\tau (n)=\sum _{\stackrel {1\leq k\leq n}{k\mid n}}1,\ \varphi (n)=\sum _{\stackrel {1\leq k\leq n}{k\perp n}}1,\ \Phi (n)=\sum _{\stackrel {1\leq k\leq n}{k{\underline {\perp }}n}}1$ n k prime to n {k ⊥ n} k divides n − 1 {k>0 | n − 1} k strongly prime to n {k ${\underline {\perp }}$ n} Φ(n) Sum Prod n − Φ(n) 0 {} {1} {} 0 0 1 0 1 {1} {} {1} 1 1 1 0 2 {1} {1} {} 0 0 1 2 3 {1,2} {1,2} {} 0 0 1 3 4 {1,3} {1,3} {} 0 0 1 4 5 {1,2,3,4} {1,2,4} {3} 1 3 3 4 6 {1,5} {1,5} {} 0 0 1 6 7 {1,2,3,4,5,6} {1,2,3,6} {4,5} 2 9 20 5 8 {1,3,5,7} {1,7} {3,5} 2 8 15 6 9 {1,2,4,5,7,8} {1,2,4,8} {5,7} 2 12 35 7 10 {1,3,7,9} {1,3,9} {7} 1 7 7 9 11 {1,2,3,4,5, 6,7,8,9,10} {1,2,5,10} {3,4,6, 7,8,9} 6 37 36288 5 12 {1,5,7,11} {1,11} {5, 7} 2 12 35 10 13 {1,2,3,4,5,6,7,8, 9,10,11,12} {1,2,3, 4,6,12} {5,7,8,9, 10,11} 6 50 277200 7 14 {1,3,5,9,11,13} {1,13} {3, 5, 9, 11} 4 28 1485 10 15 {1,2,4,7,8,11,13,14} {1,2,7,14} {4, 8, 11, 13} 4 36 4576 11 16 {1,3,5,7,9,11,13,15} {1,3,5,15} {7, 9, 11, 13} 4 40 9009 12

The strong coprimality triangle

Let divisors(n) denote the set of positive divisors of n and note that we set divisors(0) = {} (the empty set) and tau(0) = 0 by convention. This is not a mathematical definition but a convenient way to handle the case n = 0; for instance this is the way the symbolic mathematics program Maple implements this case. But also note that the sequences A027750 and A000005 start at offset 1.

With this definition, when we say "k is strongly prime to n" this corresponds to the following set equations, which subtract from the set of positive numbers prime to n the set of positive divisors of n − 1.

[n=0]  {}           minus {1}       = {},
[n=1]  {1}          minus {}        = {1},
[n=2]  {1}          minus {1}       = {},
[n=3]  {1, 2}       minus {1, 2}    = {},
[n=4]  {1, 3}       minus {1, 3}    = {},
[n=5]  {1, 2, 3, 4} minus {1, 2, 4} = {3}.

For example 1 is strongly prime to 1 and 3 is strongly prime to 5, and for every other pair (0 ≤ k ≤ n, 0 ≤ n ≤ 5) k is not strongly prime to n.

This immediately translates to the indicator function of strong coprimality, conveniently written as a triangle T(n,k) read by rows, 0 ≤ n and 0 ≤ k ≤ n.

[n=0]          0
[n=1]         0, 1
[n=2]       0, 0, 0
[n=3]      0, 0, 0, 0
[n=4]    0, 0, 0, 0, 0
[n=5]   0, 0, 0, 1, 0, 0

T(n, k) = [k is strongly prime to n] where [ ] denotes the Iverson bracket. The resulting sequence is A181837 =

0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,

Safe primes and primes not strongly prime to n

// safe primes
A005385_list := n->select(i->isprime(iquo(i,2)),
select(i->isprime(i),[$1..n])): A005385_list(800); 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719 Additionally set A181833 := n -> n - A181830(n): SavePrimes := n -> if(A181833(n) = 5, n, NULL): Now the observation is: seq(SavePrimes(i),i=0..350); A005385_list(350); 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347 In other words: The safe primes are precisely those integers n > 5 whose number of integers which are not strongly prime to n is 5. This fact can be easily visualized. The safe prime triangle The safe prime triangle is a subtriangle of the strong coprimality triangle generated by deleting the first 3 and the last 2 entries in each row. It is displayed below. If in the safe prime triangle (starting with row number 0) a row n has exactly one 0´ entry, then n+5 is a safe prime. This way all safe primes greater 5 can be found by inspecting the triangle.  n is prime and (n − 1) / 2 is an odd prime $\iff n=\Phi (n)+5.$ Proof ⇒. Since n is prime φ(n) = n − 1. Since (n − 1) / 2 is an odd prime $\tau (n-1)={\text{card}}\{1,2,(n-1)/2,n-1\}=4.$ Thus $\Phi (n)=\varphi (n)-\tau (n-1)=n-5.$ Proof ⇐. Exercise? Super safe primes and super duper safe primes and ... // safe primes A005385_list := n->select(i -> isprime(iquo(i,2)), select(i -> isprime(i),[$1..n])):

// supersafe primes
A181841_list := n->select(i -> isprime(iquo(i,3)),
select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n]))): A181841_list(5000); 7, 11, 23, 59, 179, 383, 503, 719, 1319, 1439, 1823, 2579, 2903, 3119, 3779, 4283, 4679, 4703 Of course this process can be continued. So let us state it in a concise form. SuperPrimes := proc(n, L) local sel, l; sel := (k, M) -> select(i -> isprime(iquo(i,k)),M); select(i -> isprime(i),[$1..n]);
for l in L do sel(l, %) od end:

With this little machine I can generate more new prime sequences than I could scribble in the margins of this page. So let us look only at a few basic instances.

 SuperPrimes     (110, ) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109 SuperPrimes      (1000, ) 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983 SuperPrimes     (600, ) 7, 11, 17, 23, 41, 53, 59, 71, 89, 113, 131, 179, 239, 251, 269, 293, 311, 383, 419, 449, 491, 503, 521, 593, 599 SuperPrimes     (6000, [2,3]) 7, 11, 23, 59, 179, 383, 503, 719, 1319, 1439, 1823, 2579, 2903, 3119, 3779, 4283, 4679, 4703, 5099, 5639, 5939 SuperPrimes     (80000,[2,3,5]) 11, 59, 1319, 5099, 5939, 12659, 21059, 24659, 44819, 49019, 62639, 74759, 76919 SuperPrimes   (40000,[2,3,7]) 23, 503, 8819, 10079, 13523, 18743, 23099, 23603, 26459, 28643, 32603, 37463, 39983

Case  are the prime numbers,  the safe primes,  is A162337, [2, 3] are the super-safe primes. The nice thing is that you can call this function with any list of positive integers [a,b,c,...,o]. Have fun exploring!

Strong coprime primes

The notions considered above can be constrained (or reduced) to the domain of nonnegative primes (yes, -2 is also a prime, though not a very popular one). This is what we will do now. There is no standard terminology for the classical case of coprimality on which we can build here. However, note that 3 out of the 4 sequences describing the classical case of coprime primes are already in the database (see the link table in the summary below).

 n strongly prime to n{k ${\underline {\perp }}$ n} primes stronglyprime to n Card Sum Prod π(n) − Card   AX 0 {} {} 0 0 1 0 1 {1} {} 0 0 1 0 2 {} {} 0 0 1 1 3 {} {} 0 0 1 2 4 {} {} 0 0 1 2 5 {3} {3} 1 3 3 2 6 {} {} 0 0 1 3 7 {4, 5} {5} 1 5 5 3 8 {3, 5} {3, 5} 2 8 15 2 9 {5, 7} {5, 7} 2 12 35 2 10 {7} {7} 1 7 7 3 11 {3, 4, 6, 7, 8, 9} {3, 7 } 2 10 21 3 12 {5, 7} {5, 7} 2 12 35 3 13 {5, 7, 8, 9, 10, 11} {5, 7, 11} 3 23 385 3 14 {3, 5, 9, 11} {3, 5, 11} 3 19 165 3 15 {4, 8, 11, 13} {11, 13} 2 24 143 4 16 {7, 9, 11, 13} {7, 11, 13} 3 31 1001 3

Note that AX(n) = A059957(n-1) for n ≥ 2. Although AX(n) has a more natural and fundamental definition, AX(n) = π(n) - A181834(n), and, more important, future work would profit if all 8 sequences in the two tables above are enumerated uniformly, I will not submit it to stay in accordance with OEIS submission policy and only add some remarks to A059957.

From the comments in A059957 we see that if AX(n) = 2, then n and n − 1 are prime powers (in the sense which does not force 1 to be a prime power).

seq(if(AX(n) = 2, n, NULL),n=0..300);
3, 4, 5, 8, 9, 17, 32, 128, 257,

The related sequences A006549 and A120430 assume or imply that 1 is a prime power. But since we are talking about pairs of integers the most natural sequence in this context is possibly:

union(seq(if(AX(n)=2,{n-1,n},NULL),n=0..300));
2, 3, 4, 5, 7, 8, 9, 16, 17, 31, 32, 127, 128, 256, 257,

With this definition no 1´ annoys here the lordly Fermat and Mersenne primes anymore. However, this sequence is not (yet) in the database. Finally we translate the formulas given by Labos E. in A059957 to our setup. For n ≥ 2

AX(n) = A001221(n^2-n)
= A001221(n-1)+A001221(n)
= A001221(A002378(n-1)).

Robert P. Munafo's notable sequence

Citing from the A069354 definition: Lowest base with simple divisibility test for n primes; smallest B such that ω(B) + ω(B − 1) = n. Example: a(4) = 15 because in base 15 you can test for divisibility by 4 different primes (3 and 5 directly, 2 and 7 by "casting out 14's").

A069354_list := proc(n) local i, L, Max;
Max := 1; L := NULL;
for i from 2 to n do
if nops(numtheory[factorset](i*(i-1))) = Max
then Max := Max + 1; L := L,i fi;
od;
L end:

A069354_list(720);
2, 3, 6, 15, 66, 210, 715,

# And now compare with:

B069354_list := proc(n) local i, L, Max;
Max := 0; L := NULL;
for i from 0 to n do
if AX(i) > Max # for AX see Maple code below
then Max := AX(i); L := L,i fi;
od;
L end:

# Both sequences are identical, though the
# second computation is much slower.

Thus in our setup Munafo's A069354 lists those indices of AX (the number of primes ≤ n that are not strongly prime to n) which increase for the first time the value relative to all predecessors (new maximum).

Now, what happens if we use (the corresponding) A051953 (number of primes ≤ n that are not prime to n) instead of AX in the above search? Lo and behold! We get the primorial numbers A002110! In turn this leads us to look at the prime factors of Munafo's sequence:

2, 3, 2*3, 3*5, 2*3*11, 2*3*5*7, 5*11*13, 5*7*11*19,
3*13*23*43,3*7*17*23*31, 5*11*17*19*41, 5*7*11*19*29*53,
2*7*11*13*23*31*41

Can you spot a pattern?

Min and max values of the set of strong coprimes

seq(min(op(StrongCoprimes(i))),i=0..20);
∞, 1, ∞, ∞, ∞, 3, ∞, 4, 3, 5, 7, 3, 5, 5, 3, 4, 7, 3, 5, 4, 3
seq(max(op(StrongCoprimes(i))),i=0..18);
-∞, 1, -∞, -∞, -∞, 3, -∞, 5, 5, 7, 7, 9, 7, 11, 11, 13, 13, 15

We will set the minimum and and the maximum of the empty set to 0, by convention. The corresponding sequences are A181839 and 181840.

Summary

 card sum prod #n - card k prime to n A000010 A023896 A001783 A051953 p prime to n A048865 A066911 A066838 A001221 k strongly prime to n A181830 A181831 A181832 A181833 p strongly prime to n A181834 A181835 A181836 A059957
 indicator [k ${\underline {\perp }}$ n] A181837 indicator prime [p ${\underline {\perp }}$ n] A181838 mink{k ${\underline {\perp }}$ n} A181839 maxk{k ${\underline {\perp }}$ n} A181840 safe primes A005385 super safe primes A181841

Maple code

with(numtheory):

Primes      := n -> select(k->isprime(k),{$1..n}): divisorial := proc(n) local i; mul(i,i=divisors(n)) end: coprimorial := proc(n) local i; mul(i,i=select(k->igcd(k,n)=1,[$1..n])) end:

Triangle := proc(N, C)
local T, L, k, n;
for n from 0 to N do
T := C(n);
L := NULL;
for k from 0 to n do
L := L, if(member(k,T),1,0)
od;
print(L)
od
end:

############ coprimality ###################

Coprimes := n -> select(k->igcd(k,n)=1,{$1..n}): A000010 := n -> nops(Coprimes(n)): A023896 := proc(n) local i; add(i,i=Coprimes(n)) end: A001783 := proc(n) local i; mul(i,i=Coprimes(n)) end: # These functions can also be be computed as A000010a := n -> if(n=0,0,phi(n)): A023896a := n -> if(n<2,n,n*phi(n)/2): A001783a := n -> if(n=0,1,coprimorial(n)): CoprimePrimes := n -> Primes(n) intersect Coprimes(n): A048865 := n -> nops(CoprimePrimes(n)): A066911 := proc(n) local i; add(i,i=CoprimePrimes(n)) end: A066838 := proc(n) local i; mul(i,i=CoprimePrimes(n)) end: # These functions can also be be computed as CP := n -> Primes(n) minus factorset(n): A048865a := n -> nops(CP(n)): A066911a := proc(n) local i; add(i,i=CP(n)) end: A066838a := proc(n) local i; mul(i,i=CP(n)) end: CoprimalityTriangle := n -> Triangle(n,Coprimes): CoprimesTriangle := n -> Triangle(n,CoprimePrimes): ############ strong coprimality ################### StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
A181830 := n -> nops(StrongCoprimes(n)):
A181831 := proc(n) local i; add(i,i=StrongCoprimes(n)) end:
A181832 := proc(n) local i; mul(i,i=StrongCoprimes(n)) end:

# These functions can also be be computed as
A181830a := n -> if(n=0,0,phi(n)-tau(n-1)):
A181831a := n -> if(n<2,n,n*phi(n)/2-sigma(n-1)):
A181832a := n -> if(n=0,1,coprimorial(n)/divisorial(n-1)):

StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A181834 := n -> nops(StrongCoprimePrimes(n)):
A181835 := proc(n) local i; add(i,i=StrongCoprimePrimes(n)) end:
A181836 := proc(n) local i; mul(i,i=StrongCoprimePrimes(n)) end:
AX      := n -> nops(Primes(n)) - nops(StrongCoprimePrimes(n)):

# These functions can also be be computed as
SCP := n -> Primes(n) minus factorset((n-1)*n):
A181834a := n -> nops(SCP(n)):
A181835a := proc(n) local i; add(i,i=SCP(n)) end:
A181836a := proc(n) local i; mul(i,i=SCP(n)) end:
AXa      := n -> if`(n<2,0,nops(factorset((n-1)*n))):

StrongCoprimalityTriangle  := n -> Triangle(n,StrongCoprimes):
StrongCoprimePrimesTriangle:= n -> Triangle(n,StrongCoprimePrimes):

Acknowledgment

While writing this page I was inspired by several sequences in the database. The authors of the (non classical) sequences which were most valuable to me are: Lábos Elemér (A048865, A051953, A059957), Leroy Quet (A066911, A066838, A131187), R. P. Munafo (A069354) and Olivier Gérard (A023896).