A020653 -id:A020653 - cp's OEIS frontend

A352911 Cantor's List: Pairs (i, j) of relatively prime positive integers sorted first by i + j then by i.

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

Offset: 1

N. J. A. Sloane, Apr 09 2022

a(2*n-1) / a(2*n) is the n-th fraction in Cantor's enumeration of the positive rational numbers. - Peter Luschny, Oct 10 2023

			The first few pairs are, seen as an irregular triangle:
  [1, 1],
  [1, 2], [2, 1],
  [1, 3], [3, 1],
  [1, 4], [2, 3], [3, 2], [4, 1],
  [1, 5], [5, 1],
  [1, 6], [2, 5], [3, 4], [4, 3], [5, 2], [6, 1],
  [1, 7], [3, 5], [5, 3], [7, 1],
  [1, 8], [2, 7], [4, 5], [5, 4], [7, 2], [8, 1],
  [1, 9], [3, 7], [7, 3], [9, 1],
  ...

N. J. A. Sloane, Table of n, a(n) for n = 1..9914
Georg Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik 84 (1878), 242-258, (p. 250).
N. J. A. Sloane, List of the 4957 pairs (i,j) with i+j <= 127. [Note this is not a b-file.]
Index entries for sequences related to enumerating the rationals

Cf. A352909, A020652 or A038566 (i-coordinates), A020653 (j-coordinates), A366191.

CantorsList := proc(upto) local C, F, n, t, count;
C := NULL; count := 0:
for n from 2 while count < upto do
    F := select(t -> igcd(t, n-t) = 1, [$1..n-1]);
    C := C, seq([t, n - t], t = F);
    count := count + nops(F) od:
ListTools:-Flatten([C]) end:
CantorsList(40);  # Peter Luschny, Oct 10 2023

A352911row[n_]:=Select[Array[{#,n-#}&,n-1],CoprimeQ[First[#],Last[#]]&];
Array[A352911row,10,2] (* Generates 10 rows *) (* Paolo Xausa, Oct 10 2023 *)

from math import gcd
from itertools import chain, count, islice
def A352911_gen(): # generator of terms
    return chain.from_iterable((i,n-i) for n in count(2) for i in range(1,n) if gcd(i,n-i)==1)
A352911_list = list(islice(A352911_gen(),30)) # Chai Wah Wu, Oct 10 2023

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

A157813 Denominators 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, 1, 2, 3, 1, 1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 6, 7, 5, 3, 1, 1, 2, 4, 5, 7, 8, 9, 7, 3, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 7, 5, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 11, 9, 5, 3, 1, 1, 2, 4, 7, 8, 11, 13, 14, 15, 13, 11, 9, 7, 5, 3, 1, 1, 2, 3, 4

Offset: 1

Ron R. King, Mar 07 2009

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

Cf. A157807 (numerators), A038567.

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::odd 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(s - i)
  for i in range(s, 0, -1):
    if gcd(i, s + 1 - i) != 1: continue
    print(s + 1 - i)
# Hiroaki Yamanouchi, Oct 06 2014

a(58)-a(83) from 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

A111879 Numerators of array which counts positive rational numbers (not including natural numbers).

Original entry on oeis.org

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

Offset: 3

Wolfdieter Lang, Aug 23 2005

Denominators are given by A111880.
The sequence of row lengths is [1, 1, 3, 1, 5, 3, 5, 3, 9, 3, 11, 5, 7, 7, ...] = A000010(n)-1 = phi(n)-1, with Euler's totient function phi(n).
For n>=3 delete from the list [seq(j/n-j,j=1..n-2)] the natural numbers and the ratios p/q with (p,q) not 1 (p and q not relatively prime, i.e., p and q have a common divisor >1).

			Triangle begins:
  [1],
  [1],
  [1, 2, 3],
  [1],
  [1, 2, 3, 4, 5],
  [1, 3, 5],
  [1, 2, 4, 5, 7],
  [1, 3, 7],
  ...
The corresponding ratios are:
  [1/2],
  [1/3],
  [1/4, 2/3, 3/2],
  [1/5],
  [1/6, 2/5, 3/4, 4/3, 5/2],
  [1/7, 3/5, 5/3],
  [1/8, 2/7, 4/5, 5/4, 7/2],
  [1/9, 3/7, 7/3],
  ...

P. Dienes, The Taylor Series, Dover 1957, p. 8, eq.(1).

Wolfdieter Lang, Array of ratios and more.

Row sums give A111881(n)/A069220(n), n>=3, see the W. Lang link.
Cf. A020652/A020653 if natural numbers are included.
Cf. A111880.

a(n, k) = numerator(r(n, k)), n>=3, k=1..phi(n)-1, with phi(n) = A000010(n) (Euler's totient function) and the ratios r(n, k) defined for row n above.

A071912 a(0) = 0, a(1) = 1; to get a(n+1) for n >= 1, let m = a(n) and consider in turn the numbers k = m-1, m-2, ..., 2, 1, m+1, m+2, m+3, ... until reach a k such that gcd(m,k) = 1 and m/k is different from all a(i)/a(i+1) for i = 0, ..., n-1.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Jun 13 2002

A version of a greedy construction of an integer-valued function a such that a(n)/a(n+1) runs through all nonnegative rationals exactly once.

After initial 0, odd-indexed terms are integers in order with m repeated phi(m) times; even-indexed terms are the corresponding numbers <= m and relatively prime to m, in descending order. - Franklin T. Adams-Watters, Dec 06 2006

			After [0 1 1 2 1 3 2] we have seen the fractions 0/1, 1/1, 1/2, 2/1, 1/3, 3/2; we consider k = 1, 3, 4, 5, ...; the first of these that gives a new ratio is k=3, giving 2/3, so the next term is 3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, FORTRAN program

Cf. A002487.
Bisections: A038567 and essentially A020653.
Cf. A038566.

Following Franklin T. Adams-Watters's comment.
import Data.List (transpose)
a071912 n = a071912_list !! n
a071912_list = 0 : concatMap f [1..] where
   f x = concat $ transpose [take (length tots) $ repeat x, reverse tots]
         where tots = a038566_row x
-- Reinhard Zumkeller, Dec 16 2013

a[0] = 0; a[1] = a[2] = 1; a[n_] := a[n] = Module[{m = a[n-1], ff = Table[ a[i]/a[i+1], {i, 0, n-2}], ok}, ok := GCD[m, k] == 1 && FreeQ[ff, m/k]; For[k = m-1, k >= 1, k--, If[ok, Return[k]]]; For[k = m+1, True, k++, If[ok, Return[k]]]]; Table[a[n], {n, 0, 89}] (* Jean-François Alcover, Oct 28 2017 *)

A111880 Denominators of array which counts positive rational numbers (not including natural numbers).

Original entry on oeis.org

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

Offset: 3

Wolfdieter Lang, Aug 23 2005

Numerators are given by A111879.

The method to obtain the rationals r(n,k) for row n is described under A111879.

			Triangle begins:
  [2],
  [3],
  [4, 3, 2],
  [5],
  [6, 5, 4, 3, 2],
  [7, 5, 3],
  [8, 7, 5, 4, 2],
  [9, 7, 3],
  ...
The corresponding rationals are:
  [1/2],
  [1/3],
  [1/4, 2/3, 3/2],
  [1/5],
  [1/6, 2/5, 3/4, 4/3, 5/2],
  [1/7, 3/5, 5/3],
  [1/8, 2/7, 4/5, 5/4, 7/2],
  [1/9, 3/7, 7/3],
  ...

P. Dienes, The Taylor Series, Dover 1957, p. 8, eq.(1).

Wolfdieter Lang, Array of ratios and more.

Cf. A020652/A020653 if natural numbers are included.

Cf. A111879.

a(n, k) = denominator(r(n, k)), n>=3, k=1..phi(n)-1, with phi(n) = A000010(n) (Euler's totient function) and the ratios r(n, k) are defined for row n in A111879.

A185169 Cantor's ordering of positive rational numbers, where a(n) is the balanced ternary representation of the "factorization" of the positive rational number into terms of A186285.

Original entry on oeis.org

0, 2, 1, 20, 10, 20001, 21, 12, 10002, 200, 100, 22, 201, 20011, 10022, 102, 11, 2000, 210, 120, 1000, 20000, 2001, 10202, 20101, 1002, 10000, 20000000010, 2010, 1020, 10000000020, 202, 20000000011, 20010, 12002, 122, 211, 21001, 10020, 10000000022, 101, 200000, 2100, 1200, 100000, 20021, 200001, 212, 20000010012, 20100, 2011, 1022, 10200, 10000020021, 121, 100002, 10012

Offset: 1

Daniel Forgues, Feb 19 2011

nonn

The balanced ternary digits {-1,0,+1} are represented here as {2,0,1}.

The "factorization" of positive rational numbers into prime powers of the form p^(3^k), k >= 0, (A186285) and their multiplicative inverses, allows each of those prime powers and their multiplicative inverses to be used at most once, since this corresponds to the balanced ternary representation of the exponents of the prime powers p^a and their multiplicative inverses of the prime factorization of positive rational numbers.

			The balanced ternary digits {-1,0,+1} are represented here as {2,0,1}.
n  num+den          Factors from A186285  Balanced ternary representation
1     2      1 / 1     Empty product                  0
2     3      1 / 2     (1/2)                          2
3     3      2 / 1     2                              1
4     4      1 / 3     (1/3)                          20
5     4      3 / 1     3                              10
6     5      1 / 4     (1/8)*2                        20001
7     5      2 / 3     (1/3)*2                        21
8     5      3 / 2     3*(1/2)                        12
9     5      4 / 1     8*(1/2)                        10002
10    6      1 / 5     (1/5)                          200
11    6      5 / 1     5                              100

OEIS Wiki, Cantor ordering of positive rational numbers

Cf. A020652, A020653, A186285, A186286, A186287, A050376.

A048706 XOR-conjugate rules of 1-D cellular automata rules given in A048705.

Original entry on oeis.org

150, 90, 2523490710, 199931532107794273605284333428918544790, 226413559313153607979257138616992421290

Offset: 1

Antti Karttunen, Mar 09 1999

nonn

In hexadecimal this sequence looks like: 96,5A,96696996,96696996699696696996966996696996,
AA55AA55AA55AA5555AA55AA55AA55AA,
9966669966999966996666996699996666999966996666996699996699666699669999 6699666699669999669966669999666699669999669966669966999966, ...

Index entries for sequences related to cellular automata

# Other procedures as with A048705
rule90x150combination_xored := proc(n) local r,d,p,q,j,s,k,pattern;
p := extended_A020652[ n ]; # the Rule 150 component [ 0,1,op(A020652) ]
q := extended_A020653[ n ]; # the Rule 90 component [ 1,0,op(A020653) ]
r := p+q; # radius of CA.
d := (2*r)+1; # diameter of CA, including the cell itself.
s := 0; for k from 0 to (2^d)-1 do if(bit_i(k,r) <> bit_i(rule90(rule150(k,p),q),(2*r))) then s := s + 2^k; fi; od; RETURN(s); end;

A054430 Simple self-inverse permutation of natural numbers: List each clump of phi(n) numbers (starting from phi(2) = 1) in reverse order.

Original entry on oeis.org

1, 3, 2, 5, 4, 9, 8, 7, 6, 11, 10, 17, 16, 15, 14, 13, 12, 21, 20, 19, 18, 27, 26, 25, 24, 23, 22, 31, 30, 29, 28, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 45, 44, 43, 42, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 63, 62, 61, 60, 59, 58, 71, 70, 69, 68, 67, 66, 65, 64, 79

Offset: 1

Antti Karttunen

Index entries for sequences that are permutations of the natural numbers

Maps fractions between A020652/A020653 and A020653/A020652.

cp's OEIS Frontend

A352911 Cantor's List: Pairs (i, j) of relatively prime positive integers sorted first by i + j then by i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

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

A157813 Denominators 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

A111879 Numerators of array which counts positive rational numbers (not including natural numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A071912 a(0) = 0, a(1) = 1; to get a(n+1) for n >= 1, let m = a(n) and consider in turn the numbers k = m-1, m-2, ..., 2, 1, m+1, m+2, m+3, ... until reach a k such that gcd(m,k) = 1 and m/k is different from all a(i)/a(i+1) for i = 0, ..., n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A111880 Denominators of array which counts positive rational numbers (not including natural numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A185169 Cantor's ordering of positive rational numbers, where a(n) is the balanced ternary representation of the "factorization" of the positive rational number into terms of A186285.

Views

Author

Keywords