A181835 -id:A181835 - cp's OEIS frontend

A181830 The number of positive integers <= n that are strongly prime to n.

0, 0, 0, 0, 0, 1, 0, 2, 2, 2, 1, 6, 2, 6, 4, 4, 4, 11, 4, 12, 6, 6, 6, 18, 6, 12, 9, 14, 8, 22, 6, 22, 14, 14, 12, 20, 8, 27, 16, 20, 12, 32, 10, 34, 18, 18, 16, 42, 14, 32, 17, 26, 20, 46, 16, 32, 20, 28, 24, 54, 14, 48, 28, 32, 26, 41, 16

Offset: 0

Peter Luschny, Nov 17 2010

k is strongly prime to n if and only if k is relatively prime to n and k does not divide n - 1.
It is conjectured (see Scroggs link) that a(n) is also the number of cardboard braids that work with n slots. - Matthew Scroggs, Sep 23 2017
a(n) is odd if and only if n is in A002522 but n <> 2. - Robert Israel, Jun 20 2018

			a(11) = card({1,2,3,4,5,6,7,8,9,10} - {1,2,5,10}) = card({3,4,6,7,8,9}) = 6.

Robert Israel, Table of n, a(n) for n = 0..10000
Peter Luschny, Strong coprimality
Matthew Scroggs, Braiding, pt. 2. Two results and a conjecture

Cf. A000005, A000010, A002522, A050384, A181831, A181832, A181833, A181834, A181835, A181836.

a[0]=0; a[1]=0; a[n_ /; n > 1] := Select[Range[n], CoprimeQ[#, n] && !Divisible[n-1, #] &] // Length; Table[a[n], {n, 0, 66}] (* Jean-François Alcover, Jun 26 2013 *)

a(n)=if(n<2, 0, eulerphi(n)-numdiv(n-1));
for (i=0, 66, print1(a(i), ", ")) \\ Michel Marcus, May 22 2017

def isstrongprimeto(k, n): return not(k.divides(n - 1)) and gcd(k, n) == 1
print([sum(int(isstrongprimeto(k, n)) for k in srange(n+1)) for n in srange(67)])
# Peter Luschny, Dec 03 2023

a(n) = phi(n) - tau(n-1) for n > 1, where phi(n) = A000010(n) and tau(n) = A000005(n).

Corrected a(1) to 0 by Peter Luschny, Dec 03 2023

A181832 The product of the positive integers <= n that are strongly prime to n.

Original entry on oeis.org

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, 124672148625024, 4865140665

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.
a(n) = A001783(n) / A007955(n-1) if n > 0 and a(0) = 1.
For 0 we have the empty product, giving 1. - Daniel Forgues, Aug 03 2012
From Robert G. Wilson v, Aug 04 2012: (Start)
Records appear at positions 0, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, ....
Except for 0 and 9, all records appear at prime positions and beginning with the sixth term, are == 0 (mod 100).
There are some primes which are not records: 2, 3, 61, 73, 109, 151, 181, 193, 229, 241, 271, 313, 349, 421, 433, 463, ....
Anti-records appear at positions 6, 10, 12, 14, 15, 18, 20, 24, 30, 36, 42, 48, 60, 66, 70, 78, 84, 90, 96, ..., and their values are odd. (End)

			a(11) = 3 * 4 * 6 * 7 * 8 * 9 = 36288.

Robert G. Wilson v, Table of n, a(n) for n = 0..1000
Peter Luschny, Strong coprimality.

Cf. A181830, A181831, A181833, A181834, A181835, A181836, A001783, A007955.

with(numtheory):
StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
A181832 := proc(n) local i; mul(i,i=StrongCoprimes(n)) end:
coprimorial := proc(n) local i; mul(i,i=select(k->igcd(k,n)=1,[$1..n])) end:
divisorial  := proc(n) local i; mul(i,i=divisors(n)) end:
A181832a := n -> `if`(n=0,1,coprimorial(n)/divisorial(n-1)):

f[n_] := Times @@ Select[ Range@ n, GCD[#, n] == 1 && Mod[n - 1, #] != 0 &]; Array[f, 27, 0] (* Robert G. Wilson v, Aug 03 2012 *)

A181831 The sum of positive integers <= n that are strongly prime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 0, 9, 8, 12, 7, 37, 12, 50, 28, 36, 40, 105, 36, 132, 60, 84, 78, 217, 72, 190, 125, 201, 128, 350, 90, 393, 224, 267, 224, 366, 168, 575, 304, 408, 264, 730, 210, 807, 396, 456, 428, 1009, 336, 905, 443

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.

a(n) = A023896(n) - A000203(n-1) if n > 1 and a(n) = 0 for n = 0,1.

			a(11) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 - 1 - 2 - 5 - 10 = 37.

Peter Luschny, Strong coprimality.

Cf. A181830, A181832, A181833, A181834, A181835, A181836, A023896, A000203.

with(numtheory):
A181831 := n -> `if`(n<2,0,n*phi(n)/2-sigma(n-1)):

Join[{0,0},Table[Total[Select[Range[n],CoprimeQ[#,n]&&!Divisible[n-1,#]&]],{n,2,50}]] (* Harvey P. Dale, Apr 09 2013 *)

def isstrongprimeto(k, n): return not(k.divides(n-1)) and gcd(k, n) == 1
def a(n): return sum(k for k in srange(n + 1) if isstrongprimeto(k, n))
print([a(n) for n in range(51)])
# Alternative:
def a(n): return 0 if n < 2 else n*euler_phi(n)//2 - sigma(n - 1, 1)
# Peter Luschny, Dec 03 2023

a(0) corrected by Peter Luschny, Dec 03 2023

A181834 The number of primes <= n that are strongly prime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3, 5, 4, 5, 5, 4, 4, 6, 6, 6, 6, 6, 6, 7, 6, 7, 9, 8, 7, 7, 7, 9, 9, 8, 8, 10, 9, 10, 11, 10, 10, 12, 12, 12, 12, 11, 11, 13, 13, 12, 12, 12, 12, 14, 13, 14, 15, 14, 15, 15, 13, 15, 16, 15, 14, 16, 17

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.

			a(11) = card(primes in {3, 4, 6, 7, 8, 9}) = card({3, 7}) = 2.

Peter Luschny, Strong coprimality.

Cf. A181830, A181831, A181832, A181833, A181835, A181836, A048865.

with(numtheory):
Primes := n -> select(k->isprime(k),{$1..n}):
StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A181834 := n -> nops(StrongCoprimePrimes(n)):

strongCoprimeQ[k_, n_] := PrimeQ[k] && CoprimeQ[n, k] && !Divisible[n-1, k]; a[n_] := Select[Range[n], strongCoprimeQ[#, n]&] // Length; Table[a[n], {n, 0, 72}] (* Jean-François Alcover, Jul 23 2013 *)

A181836 The product of primes <= n that are strongly prime to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 5, 15, 35, 7, 21, 35, 385, 165, 143, 1001, 15015, 5005, 85085, 51051, 46189, 20995, 440895, 1616615, 7436429, 1716099, 2860165, 5311735, 15935205, 7436429, 215656441, 3234846615

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.

			a(11) = 3 * 7 = 21.

Peter Luschny, Strong coprimality.

Cf. A181831, A181832, A181833, A181834, A181835, A001783.

with(numtheory):
Primes := n -> select(k->isprime(k),{$1..n}):
StrongCoprimes := n -> select(k->igcd(k,n)=1,{$1..n}) minus divisors(n-1):
StrongCoprimePrimes := n -> Primes(n) intersect StrongCoprimes(n):
A181836 := proc(n) local i; mul(i,i=StrongCoprimePrimes(n)) end:

a[n_] := Times @@ Select[Range[2, n], PrimeQ[#] && CoprimeQ[#, n] && !Divisible[n-1, #] &]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 28 2013 *)

A181833 The number of positive integers <= n that are not strongly prime to n.

Original entry on oeis.org

0, 0, 2, 3, 4, 4, 6, 5, 6, 7, 9, 5, 10, 7, 10, 11, 12, 6, 14, 7, 14, 15, 16, 5, 18, 13, 17, 13, 20, 7, 24, 9, 18, 19, 22, 15, 28, 10, 22, 19, 28, 9, 32, 9, 26, 27, 30, 5, 34, 17, 33, 25, 32, 7, 38, 23, 36, 29, 34, 5, 46

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.
a(n) = n - phi(n) + tau(n-1) if n > 0 and a(0) = 0.
Here phi(n) = A000010(n) and tau(n) = A000005(n).

			a(11) = 11 - card({3,4,6,7,8,9}) = 5.

Peter Luschny, Strong coprimality.

Cf. A181830, A181831, A181832, A181834, A181835, A181836, A051953.

with(numtheory):
A181833 := n -> `if`(n=0,0,n-phi(n)+tau(n-1));
A181833a := n -> n - A181830(n);

a[n_] := Select[Range[n], Not[CoprimeQ[#, n] && !Divisible[n-1, #]] &] // Length; a[1] = 0; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 28 2013 *)

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

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

Original entry on oeis.org

1, 0, 0, 0, 3, 0, 4, 5, 3, 5, 5, 7, 7, 3, 4, 6, 7, 8, 9, 5, 7, 5, 7, 8, 9, 10, 11, 3, 5, 9, 11, 4, 8, 11, 13, 7, 9, 11, 13, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 5, 7, 11, 13, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 3, 7, 9, 11, 13, 17, 8, 11, 13, 16, 17, 19

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

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

Peter Luschny, Strong Coprimality

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

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

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

def primeto(n):
    return [p for p in range(n) if gcd(p, n) == 1]
def strongly_primeto(n):
    return [p for p in set(primeto(n)) - set((n-1).divisors())]
def A322936row(n):
    if n == 1: return [1]
    if n in [2, 3, 4, 6]: return [0]
    return sorted(strongly_primeto(n))
for n in (1..21): print(A322936row(n))

cp's OEIS Frontend

A181830 The number of positive integers <= n that are strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

Extensions

A181832 The product of the positive integers <= n that are strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A181831 The sum of positive integers <= n that are strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Extensions

A181834 The number of primes <= n that are strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A181836 The product of primes <= n that are strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A181833 The number of positive integers <= n that are not strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs