A181834 -id:A181834 - 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

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

A181835 The sum of the primes <= n that are strongly prime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 0, 5, 8, 12, 7, 10, 12, 23, 19, 24, 31, 39, 36, 53, 51, 60, 54, 64, 72, 90, 80, 82, 88, 91, 90, 119, 127, 144, 127, 129, 143, 155, 139, 160, 174, 190, 185, 226, 225, 260, 248, 256

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 = 10.

Peter Luschny, Strong coprimality.

Cf. A181830, A181831, A181832, A181834, A181836, A066911.

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):
A181835 := proc(n) local i; add(i,i=StrongCoprimePrimes(n)) end:

a[n_] := Select[Range[2, n], PrimeQ[#] && CoprimeQ[#, n] && !Divisible[n-1, #] &] // Total; Table[a[n], {n, 0, 47}] (* 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))

A069354 Lowest base with simple divisibility test for n primes; smallest B such that omega(B) + omega(B-1) = n.

Original entry on oeis.org

2, 3, 6, 15, 66, 210, 715, 7315, 38571, 254541, 728365, 11243155, 58524466, 812646121, 5163068911, 58720148851, 555409903686, 4339149420606, 69322940121436, 490005293940085, 5819629108725510, 76622240600506315

Offset: 1

Robert Munafo, Nov 19 2002

Indices of record values of primepi(n) - A181834(n) (the number of primes <= n which are not strongly prime to n). - Peter Luschny, Mar 17 2013
As pointed out by Don Reble on the SeqFan list, one has a(n) = A059958(n)+1 at least up to a(18), since so far A001221(m*(m+1)) = n (and not ">") for m = A059958(n). - M. F. Hasler, Jan 15 2014
10^13 < a(19) <= 69322940121436. - Giovanni Resta, Mar 24 2020

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

Peter Luschny, Strong coprimality, November 2010.
Robert Munafo, Low bases with many divisibility tests

Cf. A001221, A181834.

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:  # Peter Luschny, Nov 12 2010

a(n) = A059958(n) + 1 for 0 < n < 19. - Robert G. Wilson v, Feb 18 2014

More terms added using data from A059958 (see there for credits) by M. F. Hasler, Jan 15 2014
a(19)-a(21) from Michael S. Branicky, Feb 11 2023
a(22) from Michael S. Branicky, Feb 23 2023

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A181835 The sum of the 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