A038566 -id:A038566 - cp's OEIS frontend

A112484 Array where n-th row contains the primes < n and coprime to n.

2, 3, 2, 3, 5, 2, 3, 5, 3, 5, 7, 2, 5, 7, 3, 7, 2, 3, 5, 7, 5, 7, 11, 2, 3, 5, 7, 11, 3, 5, 11, 13, 2, 7, 11, 13, 3, 5, 7, 11, 13, 2, 3, 5, 7, 11, 13, 5, 7, 11, 13, 17, 2, 3, 5, 7, 11, 13, 17, 3, 7, 11, 13, 17, 19, 2, 5, 11, 13, 17, 19, 3, 5, 7, 13, 17, 19, 2, 3, 5, 7, 11, 13, 17, 19, 5, 7, 11, 13

Offset: 3

Leroy Quet, Dec 13 2005

Array's n-th row contains A048865(n) terms.
T(A005408(n),1) = 2; T(n,1) = A053669(n). - Reinhard Zumkeller, Sep 23 2011
These are the primes in row n >= 3 of A038566 (smallest positive restricted residue system modulo n). - Wolfdieter Lang, Jan 18 2017

			Row 9 is [2, 5, 7], since 2, 5 and 7 are the primes < 9 and coprime to 9.
The irregular triangle begins:
n\k 1 2  3  4  5  6  7  8 ...
3:  2
4:  3
5:  2 3
6:  5
7:  2 3  5
8:  3 5  7
9:  2 5  7
10: 3 7
11: 2 3  5  7
12: 5 7 11
13: 2 3  5  7 11
14: 3 5 11 13
15: 2 7 11 13
16: 3 5  7 11 13
17: 2 3  5  7 11 13
18: 5 7 11 13 17
19: 2 3  5  7 11 13 17
20: 3 7 11 13 17 19
21: 2 5 11 13 17 19
22: 3 5  7 13 17 19
23: 2 3  5  7 11 13 17 19
... - _Wolfdieter Lang_, Jan 18 2017

Michael De Vlieger, Table of n, a(n) for n = 3..16603 (rows 3 <= n <= 400).

Cf. A038566, A048865, A053669.

f[l_] := Block[{n}, n = Length[l] + 1; Return[Append[l, Select[Range[n - 1], PrimeQ[ # ] && Mod[n, # ] > 0 &]]];]; Flatten[Nest[f, {}, 24]] (* Ray Chandler, Dec 26 2005 *)
Table[Complement[Prime@ Range@ PrimePi@ n, FactorInteger[n][[All, 1]]], {n, 3, 23}] // Flatten (* Michael De Vlieger, Sep 04 2017 *)

from sympy import primerange, gcd
def a(n): return [i for i in primerange(1, n) if gcd(i, n)==1]
for n in range(3, 24): print(a(n)) # Indranil Ghosh, Apr 27 2017

Extended by Ray Chandler, Dec 26 2005

A157807 Numerators of fractions arranged in "antidiagonal boustrophedon" ordering with equivalent fractions removed: (1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1, 6/1, 5/2, ...).

Original entry on oeis.org

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

Offset: 1

Ron R. King, Mar 07 2009

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A157813 (denominators), A038566.

With Cantor's ordering: A020652, A020653, A352911.

R:= NULL: count:= 0:
for m from 2 while count < 100 do
  S:= select(t -> igcd(t,m-t)=1, [$1..m-1]);
  count:= count+nops(S);
  if m::even then R:= R, op(S) else R:= R, seq(m-t,t=S) fi;
od:
R; # Robert Israel, Oct 09 2023

from math import gcd
for s in range(2, 100, 2):
  for i in range(1, s):
    if gcd(i, s - i) != 1: continue
    print(i)
  for i in range(s, 0, -1):
    if gcd(i, s + 1 - i) != 1: continue
    print(i)
# Hiroaki Yamanouchi, Oct 06 2014

A-number in cross-reference corrected by R. J. Mathar, Sep 23 2009
a(19)-a(20) corrected and a(58)-a(82) added by Hiroaki Yamanouchi, Oct 06 2014
Name corrected by Andrey Zabolotskiy, Oct 10 2023

A176352 Order the positive rationals by numerator+denominator, then by numerator. a(n+1) = a(n)*r, where r is the first unused positive rational that makes a(n+1) an integer not already in the sequence.

Original entry on oeis.org

1, 2, 6, 3, 12, 4, 20, 5, 30, 45, 9, 15, 10, 25, 175, 70, 42, 7, 56, 8, 28, 21, 49, 14, 126, 168, 210, 90, 72, 16, 160, 60, 50, 225, 270, 27, 297, 33, 88, 11, 132, 231, 165, 264, 24, 54, 63, 36, 120, 75, 105, 189, 84, 462, 396, 108, 1404, 117, 65, 910, 273, 1001, 182, 13

Offset: 1

Franklin T. Adams-Watters, Apr 15 2010

It appears that this sequence is a permutation of the positive integers.
It appears that every positive rational except 1 occurs as the ratio of consecutive terms.
A218454 gives smallest numbers m such that a(m)=n; a(A176352(n))=n. - Reinhard Zumkeller, Oct 30 2012
A218535(n) = gcd(a(n),a(n+1)); A218533(n)/A218534(n) = a(n)/a(n+1). - Reinhard Zumkeller, Nov 10 2012

			After a(6)=4, we have used ratios 1/2, 2, 1/3, and 3. 1/4 would give 1, which is already used. 2/3 would give 8/3, not an integer; 3/2 would give 6, already used; and ratio 4 is already used. 1/5 would not produce an integer; next is 5, giving a(7) = 4*5 = 20.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

This ordering of the rationals is A038566/A020653.

Cf. A002487.

import Data.Ratio ((%), numerator, denominator)
import Data.List (delete)
import Data.Set (singleton, insert, member)
a176352 n = a176352_list !! (n-1)
a176352_list = 1 : f 1 (singleton 1) (concat $ drop 2 $
   zipWith (zipWith (%)) a038566_tabf $ map reverse a038566_tabf)
   where f x ws qs = h qs
           where h (r:rs) | denominator y /= 1 || v `member` ws = h rs
                          | otherwise = v : f y (insert v ws) (delete r qs)
                          where v = numerator y; y = x * r
-- Reinhard Zumkeller, Oct 30 2012

copywo(v,k)=vector(#v-1,i,v[if(i#pend,pend=concat(pend,rprat(last++)));
try=v[i-1]*pend[k];
if(denominator(try)==1&!invecn(v,i-1,try),
pend=copywo(pend,k);v[i]=try;break);
k++));v}

Definition stated more precisely by Reinhard Zumkeller, Oct 30 2012

A216327 Irregular triangle of multiplicative orders mod n for the elements of the smallest positive reduced residue system mod n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 4, 2, 1, 2, 1, 3, 6, 3, 6, 2, 1, 2, 2, 2, 1, 6, 3, 6, 3, 2, 1, 4, 4, 2, 1, 10, 5, 5, 5, 10, 10, 10, 5, 2, 1, 2, 2, 2, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 1, 6, 6, 3, 3, 2, 1, 4, 2, 4, 4, 2, 4, 2, 1, 4, 4, 2, 2, 4, 4, 2

Offset: 1

Wolfdieter Lang, Sep 28 2012

The sequence of the row lengths is phi(n) = A000010 (Euler's totient).
For the notion 'reduced residue system mod n' which has, as a set, order phi(n) = A000010(n), see e.g., the Apostol reference p. 113. Here such a system with the smallest positive numbers is used. (In the Apostol reference 'order of a modulo n' is called 'exponent of a modulo n'. See the definition on p. 204.)
See A038566 where the reduced residue system mod n appears in row n.
In the chosen smallest reduced residue system mod n one can replace each element by any congruent mod n one, and the given order modulo n list will, of course, be the same. E.g., n=5, {6, -3, 13, -16} also has the orders modulo 5:  1  4  4  2, respectively.
Each order modulo n divides phi(n). See the Niven et al. reference, Corollary 2.32, p. 98.
The maximal order modulo n is given in A002322(n).
For the analog table of orders Modd n see A216320.

			This irregular triangle begins:
n\k 1  2  3  4  5  6  7  8  9  10 11 12  13 14  15 16 17 18
1:  1
2:  1
3:  1  2
4:  1  2
5:  1  4  4  2
6:  1  2
7:  1  3  6  3  6  2
8:  1  2  2  2
9:  1  6  3  6  3  2
10: 1  4  4  2
11: 1 10  5  5  5 10 10 10  5   2
12: 1  2  2  2
13: 1 12  3  6  4 12 12  4  3   6 12  2
14: 1  6  6  3  3  2
15: 1  4  2  4  4  2  4  2
16: 1  4  4  2  2  4  4  2
17: 1  8 16  4 16 16 16  8  8  16 16 16   4 16   8  2
18: 1  6  3  6  3  2
19: 1 18 18  9  9  9  3  6  9  18  3  6  18 18  18  9  9  2
20: 1  4  4  2  2  4  4  2
...
a(3,2) = 2 because A038566(3,2) = 2 and 2^1 == 2 (mod 3), 2^2 = 4 == 1 (mod 3).
a(7,3) = 6 because A038566(7,3) = 3 and 3^1 == 3 (mod 7), 3^2 = 9 == 2 (mod 7), 3^3 = 2*3 == 6 (mod 7),  3^4 == 6*3 == 4 (mod 7), 3^5 == 4*3 == 5 (mod 7) and  3^6 == 5*3 == 1 (mod 7). The notation == means 'congruent'.
The maximal order modulo 7 is 6 = A002322(7) = phi(7), and it appears twice: A111725(7) = 2.
The maximal order modulo 14 is 6 = A002322(14) = 1*6.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth edition, Wiley, 1991.

Michael De Vlieger, Table of n, a(n) for n = 1..12232 (rows n = 1..200, flattened.)

Cf. A038566, A002322 (maximal order), A111725 (multiplicity of max order), A216320 (Modd n analog).

Cf. A086145

Table[Table[MultiplicativeOrder[k,n],{k,Select[Range[n],GCD[#,n]==1&]}],{n,1,13}]//Grid  (* Geoffrey Critzer, Jan 26 2013 *)

rowa(n) = select(x->gcd(n, x)==1, [1..n]); \\ A038566
row(n) = apply(znorder, apply(x->Mod(x, n), rowa(n))); \\ Michel Marcus, Sep 12 2023

a(n,k) = order A038566(n,k) modulo n, n >= 1, k=1, 2, ..., phi(n) = A000010(n). This is the order modulo n of the k-th element of the smallest reduced residue system mod n (when their elements are listed increasingly).

A333848 a(n) gives the sum of the odd numbers of the smallest nonnegative reduced residue system modulo 2*n + 1, for n >= 0.

Original entry on oeis.org

0, 1, 4, 9, 13, 25, 36, 32, 64, 81, 66, 121, 124, 121, 196, 225, 170, 216, 324, 240, 400, 441, 272, 529, 513, 416, 676, 560, 522, 841, 900, 570, 792, 1089, 770, 1225, 1296, 752, 1170, 1521, 1093, 1681, 1376, 1232, 1936, 1656, 1410, 1728, 2304, 1490, 2500

Offset: 0

Wolfdieter Lang, May 01 2020

The smallest nonnegative reduced residue system modulo N is the ordered set RRS(N) (written as a list) with integers k from {0, 1, ..., N-1} satisfying gcd(k, N) = 1, for N >= 1. See A038566 (with A038566(1) = 0).
If only odd members of RRS(N) are considered, name this list RRSodd(N), e.g., RRSodd(1) = [], the empty list, RRSodd(2) = [1], etc. See A216319 (but there A216319(1) = 1). The number of elements of RRSodd(N) is delta(N) = A055034(N), for N >= 2, and 0 for N = 1.
Here only numbers N = 2*n + 1 >= 1 are considered, and for the empty list RRSodd(1) a(0) is set to 0.
a(n) gives for n >= 1 also the sum of the numbers of the primitive period of the unsigned Schick sequences SBB(2*n+1, q0 = 1) (BB for Brändli and Beyne), for which 2*n + 1 satisfies A135303(n) = 1 (in Schick's notation B(2*n+1) = 1, implying initial value q0 = 1). The numbers n satisfying A135303(n) = 1 are given in A333854.
The sequence with members gcd(a(n), 2*(2*n+1)) = A333849(n) is important for a length formula for the Euler tours ET(2*n+1, q0 = 1) given in A332441(n), for n >= 1 (but A333849(n) is used only for 2*n+1 values from A333854).

			n = 4: RRSodd(9) = {1, 5, 7} with sum a(4) = 13. Schick's unsigned cycle is SBB(9, 1) = (1, 7, 5). Because A135303(4) = B(9) = 1 there is only this cycle for n = 9.

Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3..113 (with gaps), pp. 158-166.

Michael De Vlieger, Table of n, a(n) for n = 0..10000
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.

Cf. A038566, A055034, A135303, A216319, A333849, A333854.

{0}~Join~Table[Total@ Select[Range[1, m, 2], GCD[#, m] == 1 &], {m, Array[2 # + 1 &, 50]}] (* Michael De Vlieger, Oct 15 2020 *)

a(n) = if (n==0, 0, my(m=2*n+1); vecsum(select(x->((gcd(m, x)==1) && (x%2)), [1..m]))); \\ Michel Marcus, May 05 2020

apply( {A333848(n)=vecsum([2*m-1|m<-[1..n],gcd(m*2-1,n*2+1)==1])}, [0..50]) \\ M. F. Hasler, Jun 04 2020

a(n) = Sum_{j=1..delta(2*n+1)} RRSodd(2*n+1)_j, for n >= 1, with delta(k) = A055034(k). a(0) = 0 (undefined case).

A070194 List the phi(n) numbers from 1 to n-1 which are relatively prime to n; sequence gives size of maximal gap.

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 3, 2, 1, 4, 1, 4, 3, 4, 1, 4, 2, 4, 2, 4, 1, 6, 1, 2, 3, 4, 3, 4, 1, 4, 3, 4, 1, 6, 1, 4, 3, 4, 1, 4, 2, 4, 3, 4, 1, 4, 3, 4, 3, 4, 1, 6, 1, 4, 3, 2, 3, 6, 1, 4, 3, 6, 1, 4, 1, 4, 3, 4, 3, 6, 1, 4, 2, 4, 1, 6, 3, 4, 3, 4, 1, 6, 3, 4, 3, 4, 3, 4, 1, 4, 3, 4, 1, 6, 1, 4, 5, 4, 1

Offset: 3

N. J. A. Sloane, May 13 2002

Maximal gap in reduced residue system mod n.

It is an unsolved problem to determine the rate of growth of this sequence.

			For n = 10 the reduced residues are 1, 3, 7, 9; the maximal gap is a(10) = 7-3 = 4.

H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 200.

T. D. Noe, Table of n, a(n) for n=3..10000

Cf. A000010.

Cf. A038566.

a070194 n = maximum $ zipWith (-) (tail ts) ts where ts = a038566_row n
-- Reinhard Zumkeller, Oct 01 2012

f[n_] := Block[{a = Select[ Table[i, {i, n - 1}], GCD[ #, n] == 1 & ], b = {}, k = 1, l = EulerPhi[n]}, While[k < l, b = Append[b, Abs[a[[k]] - a[[k + 1]]]]; k++ ]; Max[b]]; Table[ f[n], {n, 3, 100}]

A070194(n)={my(L=1,m=1);for(k=2,n-1,gcd(k,n)>1&next;L+mM. F. Hasler, Sep 08 2012

a(n) = max(A048669(n),2) for all n>2. Indeed A048669 is obtained when going up to n+1 instead of only n-1 (because after n+1, the gaps among numbers coprime to n repeat). Since n-1 and n+1 are both coprime to n, this means that A048669(n)=2 whenever a(n)=1, but in all other cases, there is equality. - M. F. Hasler, Sep 08 2012

More terms from Robert G. Wilson v and John W. Layman, May 13 2002

A115855 Number of partitions of 1 into fractions i/j with 1<=i

Original entry on oeis.org

0, 1, 3, 6, 12, 21, 35, 58, 106, 188, 243, 493, 593, 1062, 3275, 5507, 5803, 12426, 12915, 42410, 131772, 167587, 168841, 428012, 839367, 1015501, 1968161, 5787286, 5791850, 15163758, 15170599, 28838712, 75983559, 82753547, 486356262, 1158442726, 1158464362

Offset: 1

Reinhard Zumkeller, Feb 01 2006

nonn

			a(4) = #{1/2+1/2, 1/2+1/4+1/4, 1/3+2/3, 1/3+1/3+1/3, 1/4+3/4, 1/4+1/4+1/4+1/4} = 6.

Cf. A000041, A002966, A038566, A038567, A115856, A116084.

Table[Length@ Select[Flatten[Map[IntegerPartitions[1, {#}, Rest@ Union[Flatten@ TensorProduct[#, 1/#] &@ Range@ n /. {Integer -> 0, k /; k > 1 -> 0}]] &, Range@ n], 1], Total@ # == 1 &], {n, 25}] (* Michael De Vlieger, Jul 15 2016 *) (* or *)
a[n_] := Sum[ Length@ IntegerPartitions[1, {k}, Union@ Flatten[ Table[i/j, {j, n}, {i, j-1}]]], {k, n}]; Array[a, 20] (* Giovanni Resta, Jun 15 2017 *)

A115856(n) = a(n+1) - a(n).

a(21)-a(28) from Michael De Vlieger, Jul 15 2016

More terms from Jinyuan Wang, Dec 11 2024

A228179 Irregular table where the n-th row consists of the square roots of 1 in Z_n.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 3, 5, 7, 1, 8, 1, 9, 1, 10, 1, 5, 7, 11, 1, 12, 1, 13, 1, 4, 11, 14, 1, 7, 9, 15, 1, 16, 1, 17, 1, 18, 1, 9, 11, 19, 1, 8, 13, 20, 1, 21, 1, 22, 1, 5, 7, 11, 13, 17, 19, 23, 1, 24, 1, 25, 1, 26, 1, 13, 15, 27, 1, 28, 1, 11

Offset: 2

Tom Edgar, Aug 20 2013

Each 1 starts a new row.
This is a subsequence of A020652.
Row n has A060594(n) entries.
Each row forms a subgroup of the multiplicative group of units of Z_n.

			The table starts out as follows:
  1
  1 2
  1 3
  1 4
  1 5
  1 6
  1 3 5 7
  1 8
  1 9
  1 10
  1 5 7 11
  ...

Alois P. Heinz, Rows n = 2..2000 of irregular triangle, flattened

Cf. A060594, A038566, A020652, A082568.
Cf. A070667 (second column), A358016 (second-last column).
Cf. A277776 (nontrivial square roots of 1).

T:= n-> seq(`if`(k&^2 mod n=1, k, NULL), k=1..n-1):
seq(T(n), n=2..50);  # Alois P. Heinz, Aug 20 2013

Flatten[Table[Position[Mod[Range[n]^2, n], 1], {n, 2, 50}]] (* T. D. Noe, Aug 20 2013 *)

from itertools import chain, count, islice
from sympy.ntheory import sqrt_mod_iter
def A228179_gen(): # generator of terms
    return chain.from_iterable((sorted(sqrt_mod_iter(1,n)) for n in count(2)))
A228179_list = list(islice(A228179_gen(),30)) # Chai Wah Wu, Oct 26 2022

[[i for i in [1..k-1] if (i*i).mod(k)==1] for k in [2..n]] #changing n gives you the table up to the n-th row.

A290600 Irregular triangle T(n, k) read by rows: positive numbers non-coprime to A002808(n) and smaller than A002808(n), sorted increasingly.

Original entry on oeis.org

2, 2, 3, 4, 2, 4, 6, 3, 6, 2, 4, 5, 6, 8, 2, 3, 4, 6, 8, 9, 10, 2, 4, 6, 7, 8, 10, 12, 3, 5, 6, 9, 10, 12, 2, 4, 6, 8, 10, 12, 14, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 3, 6, 7, 9, 12, 14, 15, 18

Offset: 1

Wolfdieter Lang, Aug 30 2017

The length of row n is A290599(n).

Row n gives the complement of row A038566(A002808(n), k) with respect to [1, 2, ..., A002808(n) - 1].

			The irregular triangle T(n, k) begins (N(n) = A002808(n)):
  n   N(n) \ k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1   4         2
  2   6         2  3  4
  3   8         2  4  6
  4   9         3  6
  5   10        2  4  5  6  8
  6   12        2  3  4  6  8  9 10
  7   14        2  4  6  7  8 10 12
  8   15        3  5  6  9 10 12
  9   16        2  4  6  8 10 12 14
  10  18        2  3  4  6  8  9 10 12 14 15 16
  11  20        2  4  5  6  8 10 12 14 15 16 18
  12  21        3  6  7  9 12 14 15 18
  13  22        2  4  6  8 10 11 12 14 16 18 20
  14  24        2  3  4  6  8  9 10 12 14 15 16 18 20 21 22
  15  25        5 10 15 20
  ...

Cf. A002808, A038566, A290599, A290601, A290602.

Table[With[{c = FixedPoint[n + PrimePi@ # + 1 &, n + PrimePi@ n + 1]}, Select[Range[c - 1], ! CoprimeQ[#, c] &]], {n, 12}] // Flatten (* Michael De Vlieger, Sep 03 2017 *)

T(n, k) = k-th entry in the list of increasingly sorted numbers of the set {m = 1..A002808(n)-1: gcd(n, m) not equal to 1}.

A333856 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo n by Brändli and Beyne, called mod* n.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 3, 1, 2, 4, 1, 3, 1, 2, 3, 4, 5, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 1, 2, 4, 7, 1, 3, 5, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 5, 7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 7, 9, 1, 2, 4, 5, 8, 10, 1, 3, 5, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Offset: 1

Wolfdieter Lang, Jun 26 2020

The length of row n is A023022(n), for n >= 1, with A023022(1) = 1.
See the Brändli-Beyne link for this mod* system.
This reduced residue system mod* n will be called RRS*(n). The mod* n system is defined only for numbers coprime to n. The definition of mod*(a, n), for gcd(a, n) = 1, is mod(a, n) from RRS(n) given in A038566, if mod(a, n) <= floor(n/2) and mod(-a, n) from RRS(n) otherwise. E.g., mod*(17, 10) = mod(-17, 10) = 3 because mod(17, 10) = 7 > 10/2 = 5. mod*(22, 10) is not defined because gcd(22, 10) = 2, not 1.
Compare this table with the one for the reduced residue system modulo n (called RRS(n)) from A038566. For n >= 3 RRS*(n) consists of the first half of the RRS(n) members.
Each member j of RRS*(n) stands for a reduced representative class [j]* which is given by the union of the ordinary reduced representative classes [j] and [n-j] modulo n, for n >= 3, with j from the first half of the set RRS(n) given in row n of A038566 (but with 0 for n = 1). For n = 1: [0]* = [0] (using A038566(1) = 0, not 1), representing all integers. For n = 2: [1]* = [1], representing all odd integers.
E.g., RRS*(5) = {1, 2} (always considered ordered), and [1]* = {pm1, pm4, pm5, pm9, ...} (pm for + or -), and  [2]* = {pm2, pm3, pm7, pm8, ...}. Hence RRS*(5) represents the same integers as RRS(5), but has only 2, not 4 elements (RRS*(5) is not equal to  RRS(5)).
The modular arithmetic is multiplicative but not additive for mod* n. This is based on the fact that gcd(a*b, n) = 1 if gcd(a, n) = 1 = gcd(b, n) (not valid in general for gcd(a + b, n)). E.g., 2 = mod*(92, 9) = mod*(23*4, 9) = mod*(4*4, 10) = 2, because 2 <= 4, 5 > 4, 4 <= 4, 7 > 4, hence mod*(23, 9) = mod(-23, 9) = 4, mod*(4, 9) = 4 and mod*(16, 9) = mod(-16, 9) = 2. For n = 9 the class [2]* consists of [2] union [9-2], i.e, {pm2, pm7, pm11, pm16, ...}.

			The irregular triangle T(n, k) begins:
n\k  1 2 3 4 5 6 7 8 9 ...
-----------------------------------------
1:   0
2:   1
3:   1
4:   1
5:   1 2
6:   1
7:   1 2 3
8:   1 3
9:   1 2 4
10:  1 3
11:  1 2 3 4 5
12:  1 5
13:  1 2 3 4 5 6
14:  1 3 5
15:  1 2 4 7
16:  1 3 5 7
17:  1 2 3 4 5 6 7 8
18:  1 5 7
19:  1 2 3 4 5 6 7 8 9
20:  1 3 7 9
...
-----------------------------------------
n = 9: 1 represents the union of the ordinary restricted residue classes [1] and [-1] = [8], called [1]*, 2 represents the union of [2] and [-2] = [7], called [2]*, and 4 represents the union of [4] and [-4] = [5], called [4]*. One could replace [1]* by [8]*, [2]* by [7]* and [4]* by [5]*, but here the smallest numbers 1, 2, 4 are used for RRS*(9).
Multiplication table for RRS*(9) (x is used here instead of *): 1 x 1 = 1, 1 x 2 = 2, 1 x 4 = 4; 2 x 1 = 2, 2 x 2 = 4, 2 x 4 = 1; 4 x 1 = 4, 4 x 2 = 1, 4 x 4 = 2. This is the (Abelian) cyclic group C_3.

Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.

Cf. A023022, A038566 (RRS), A333857.

Essentially the same as A182972.

RRS(n) = select(x->gcd(n, x)==1, [1..n]); \\ A038566
row(n) = if (n<=2, [n-1], my(r=RRS(n)); Vec(r, #r/2)); \\ Michel Marcus, Sep 17 2023

T(1, 1) = 0, T(2, 1) = 1, and T(n, k) = A038566(n, k) for k = 1, 2, ..., A023022(n), for n >= 3.

cp's OEIS Frontend

A112484 Array where n-th row contains the primes < n and coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A157807 Numerators of fractions arranged in "antidiagonal boustrophedon" ordering with equivalent fractions removed: (1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1, 6/1, 5/2, ...).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Python

Extensions

A176352 Order the positive rationals by numerator+denominator, then by numerator. a(n+1) = a(n)*r, where r is the first unused positive rational that makes a(n+1) an integer not already in the sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Extensions

A216327 Irregular triangle of multiplicative orders mod n for the elements of the smallest positive reduced residue system mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333848 a(n) gives the sum of the odd numbers of the smallest nonnegative reduced residue system modulo 2*n + 1, for n >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A070194 List the phi(n) numbers from 1 to n-1 which are relatively prime to n; sequence gives size of maximal gap.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A115855 Number of partitions of 1 into fractions i/j with 1<=i

Views

Author