This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/StrongCoprimality
From OeisWiki
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
I prefer the name `coprimorial´ to `phitorial´. Similarly the divisorial A007955 is defined as
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
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 b´)
iff a is prime to b and a does not divide b − 1.
We also suggest to write m 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_{p} 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)
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.
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).
n | k prime to n {k ⊥ n} |
k divides n − 1 {k>0 | n − 1} |
k strongly prime to n {k 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 |
Proof ⇒. Since n is prime φ(n) = n − 1. Since (n − 1) / 2 is an odd prime
- τ(n − 1) = card{1,2,(n − 1) / 2,n − 1} = 4.
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, [1]) |
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, [2]) |
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, [3]) |
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 [1] are the prime numbers, [2] the safe primes, [3] 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 n} |
primes strongly prime 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 n] | A181837 | indicator prime [p n] | A181838 |
min_{k}{k n} | A181839 | max_{k}{k 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).
See also
- Sequences related to Euler's totient function.
- Notation matters.
- My private copy on my website with more links.