A066657 -id:A066657 - cp's OEIS frontend

A066848 Consider sequence of fractions A066657/A066658 produced by ratios of terms in A066720; let m = smallest integer such that all fractions 1/n, 2/n, ..., (n-1)/n have appeared when we reach A066720(m) = k; sequence gives values of k; set a(n) = -1 if some fraction i/n never appears.

1, 2, 3, 2436, 520, 60, 308, 2436, 15867, 61800, 8096, 55620, 77077, 20216, 51675, 2296992, 21607, 15867, 185820, 481680, 140805, 226644, 145866, 1568928, 1076000, 187772, 5596587, 1831956, 715778, 3540060, 836535, 2296992, 3088008, 1129514, 7096775, 1995048, 2018646, 3159168, 13019136, 15293320, 6936667, 11250624, 6877463, 20475136, 3380040, 3986360, 1052424, 17566608, 5152350, 1076000, 3824694, 8897564, 2987239, 17600004, 24056230, 89537336, 23397531, 2791424, 5393780, 19344660, 5306268, 8679008, 126415359, 30486400, 29303235

Offset: 1

N. J. A. Sloane, Jan 21 2002

			3/4 does not occur until we reach A066720(401) = 2436 and then we see A066720(320)/A066720(401) = 1827/2436 = 3/4. Therefore a(4) = 2436.

Cf. A066720, A066657, A066658. A066849 gives values of m.

Corrected by John W. Layman, Feb 05 2002

Greatly extended by David Applegate, Feb 13 2002

A066849 Consider sequence of fractions A066657/A066658 produced by ratios of terms in A066720; let m = smallest integer such that all fractions 1/n, 2/n, ..., (n-1)/n have appeared when we reach A066720(m) = k; sequence gives values of m; set a(n) = -1 if some fraction i/n never appears.

Original entry on oeis.org

1, 2, 3, 401, 113, 22, 75, 401, 1986, 6547, 1110, 5949, 7952, 2445, 5578, 172617, 2590, 1986, 17471, 41341, 13631, 20900, 14063, 121563, 86009, 17648, 392866, 140171, 59293, 257162, 68370, 172617, 226693, 89942, 489653, 151601, 153287, 231508, 860521, 999664, 479352, 751180, 475540, 1312350, 246470, 287004, 84285, 1137690, 363942, 86009, 276267, 603972, 219888, 1139722, 1525515, 5227193, 1486480, 206546, 379708, 1244626, 374003, 590152, 7230480, 1903679, 1834403

Offset: 1

N. J. A. Sloane, Jan 21 2002

			3/4 does not occur until we reach A066720(401) = 2436 and then we see A066720(320)/A066720(401) = 1827/2436 = 3/4. Therefore a(4) = 401.

Cf. A066720, A066657, A066658. A066848 gives values of k.

Corrected by John W. Layman, Feb 05 2002

Greatly extended by David Applegate, Feb 13 2002

A076941 a(n) = 2^A066657(n) * 3^A066658(n).

Original entry on oeis.org

6, 18, 54, 108, 486, 972, 1944, 4374, 8748, 17496, 69984, 13122, 162, 52488, 209952, 839808, 354294, 708588, 1417176, 5668704, 22674816, 45349632, 3188646, 6377292, 12754584, 51018336, 204073344, 408146688, 3265173504, 258280326, 516560652, 1033121304

Offset: 0

Amarnath Murthy, Oct 19 2002

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Cf. A066657, A066658, A076940.

Cf. A066720, subsequence of A003586.

a076941 n = 2 ^ (a066657 n) * 3 ^ (a066658 n)
-- Reinhard Zumkeller, Nov 19 2013

Edited by Max Alekseyev, Aug 11 2013

Offset changed by Reinhard Zumkeller, Nov 19 2013

A066720 The greedy rational packing sequence: a(1) = 1; for n > 1, a(n) is smallest number such that the ratios a(i)/a(j) for 1 <= i < j <= n are all distinct.

Original entry on oeis.org

1, 2, 3, 5, 7, 8, 11, 13, 17, 18, 19, 23, 29, 31, 37, 41, 43, 47, 50, 53, 59, 60, 61, 67, 71, 73, 79, 81, 83, 89, 97, 98, 101, 103, 105, 107, 109, 113, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239

Offset: 1

N. J. A. Sloane, Jan 15 2002

Sequence was apparently invented by Jeromino Wannhoff - see the Rosenthal link.
An equivalent definition: a(1) = 1, a(2) = 2 and thereafter a(n) is the smallest number such that all a(i)*a(j) are different. - Thanks to Jean-Paul Delahaye for this comment. - N. J. A. Sloane, Oct 01 2020
If you replace the word "ratio" with "difference" and start from 1 using the same greedy algorithm you get A005282. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 15 2002
Taking a(n) as the smallest number such that the pairwise sums a(i)+a(j) (iA011185. - Jean-Paul Delahaye, Oct 02 2020. [This replaces an incorrect comment.]
Does every rational number appear as a ratio? See A066657, A066658.
Contains all primes. Differs from A066724 in that the latter forbids only the products of distinct terms. - Ivan Neretin, Mar 02 2016

			After 5, 7 is the next member and not 6 as 6*1 = 2*3.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
David Applegate, First 48186 terms of A066721 and their factorizations (implies first 8165063 terms of current sequence)
Rainer Rosenthal, Posting to de.rec.denksport, Jan 15 2002
Robert E. Sawyer, Is there such a sequence? Posting by r.e.s. to sci.math newsgroup, Jan 13, 2002

Consists of the primes together with A066721.
Cf. A011185, A005282, A066724, A066775, A079850, A079852.
For the rationals that are produced see A066657/A066658 and A066848, A066849.

import qualified Data.Set as Set (null)
import Data.Set as Set (empty, insert, member)
a066720 n = a066720_list !! (n-1)
a066720_list = f [] 1 empty where
   f ps z s | Set.null s' = f ps (z + 1) s
            | otherwise   = z : f (z:ps) (z + 1) s'
     where s' = g (z:ps) s
           g []     s                      = s
           g (x:qs) s | (z * x) `member` s = empty
                      | otherwise          = g qs $ insert (z * x) s
-- Reinhard Zumkeller, Nov 19 2013

A[1]:= 1:
F:= {1}:
for n from 2 to 100 do
for k from A[n-1]+1 do
Fk:= {k^2, seq(A[i]*k,i=1..n-1)};
if Fk intersect F = {} then
A[n]:= k;
F:= F union Fk;
break
fi
od
od:
seq(A[i],i=1..100); # Robert Israel, Mar 02 2016

s={1}; xok := Module[{}, For[i=1, i<=n, i++, For[j=1; k=Length[dl=Divisors[s[[i]]x]], j<=k, j++; k--, If[MemberQ[s, dl[[j]]]&&MemberQ[s, dl[[k]]], Return[False]]]]; True]; For[n=1, True, n++, Print[s[[n]]]; For[x=s[[n]]+1, True, x++, If[xok, AppendTo[s, x]; Break[]]]] (* Dean Hickerson *)
a[1] = 1; a[n_] := a[n] = Block[{k = a[n - 1] + 1, b = c = Table[a[i], {i, 1, n - 1}], d}, While[c = Append[b, k]; Length[ Union[ Flatten[ Table[ c[[i]]/c[[j]], {i, 1, n}, {j, 1, n}]]]] != n^2 - n + 1, k++ ]; Return[k]]; Table[ a[n], {n, 1, 75} ] (* Robert G. Wilson v *)
nmax = 100; a[1] = 1; F = {1};
For[n = 2, n <= nmax, n++,
For[k = a[n-1]+1, True, k++, Fk = Join[{k^2}, Table[a[i]*k, {i, 1, n-1}]] // Union; If[Fk ~Intersection~ F == {}, a[n] = k; F = F ~Union~ Fk; Break[]
]]];
Array[a, nmax] (* Jean-François Alcover, Mar 26 2019, after Robert Israel *)

{a066720(m) = local(a,rat,n,s,new,b,i,k,j); a=[]; rat=Set([]); n=0; s=0; while(sKlaus Brockhaus, Feb 23 2002

More terms from Dean Hickerson, Klaus Brockhaus and David Applegate, Jan 15 2002

Entry revised by N. J. A. Sloane, Oct 01 2020.

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jun 09 2013

The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow].

Sum(A226314(n,k)/A054531(n,k): 1<=k<=n) = A226555(n)/A040001(n). - Reinhard Zumkeller, Jun 10 2013

			Triangle begins:
[1]
[1, 2]
[1, 2, 3]
[1, 3, 3, 4]
[1, 2, 3, 4, 5]
[1, 4, 5, 5, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 5, 3, 7, 5, 7, 7, 8]
[1, 2, 7, 4, 5, 8, 7, 8, 9]
[1, 6, 3, 7, 9, 8, 7, 9, 9, 10]
...
The resulting triangle of fractions begins:
1,
1/2, 2,
1/3, 2/3, 3,
1/4, 3/2, 3/4, 4,
1/5, 2/5, 3/5, 4/5, 5,
...

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.
Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Cf. A002262.

Cf. A037161, A037162, A066657, A066658.

a226314 n k = n - (n - k) `div` gcd n k
a226314_row n = a226314_tabl !! (n-1)
a226314_tabl = map f $ tail a002262_tabl where
   f us'@(_:us) = map (v -) $ zipWith div vs (map (gcd v) us)
     where (v:vs) = reverse us'
-- Reinhard Zumkeller, Jun 10 2013

f:=(i,j) -> j+(i-j)/gcd(i,j);
g:=n->[seq(f(i,n),i=1..n)];
for n from 1 to 20 do lprint(g(n)); od:

A066658 Denominators of rational numbers produced in order by A066720(j)/A066720(i) for i >= 1, 1 <= j

Original entry on oeis.org

1, 2, 3, 3, 5, 5, 5, 7, 7, 7, 7, 8, 4, 8, 8, 8, 11, 11, 11, 11, 11, 11, 13, 13, 13, 13, 13, 13, 13, 17, 17, 17, 17, 17, 17, 17, 17, 18, 9, 6, 18, 18, 9, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 29, 29

Offset: 0

N. J. A. Sloane, Jan 18 2002

Does every rational number in range (0,1) appear?

a(0) = 1 by convention.

			Sequence of rationals begins 1, 1/2, 1/3, 2/3, 1/5, 2/5, 3/5, 1/7, 2/7, 3/7, 5/7, 1/8, 1/4, 3/8, 5/8, 7/8, 1/11, 2/11, ...

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

Cf. A066657 (numerators), A066720.

import Data.List (inits)
import Data.Ratio ((%), denominator)
a066658 n = a066658_list !! n
a066658_list = map denominator
   (1 : (concat $ tail $ zipWith (\u vs -> map (% u) vs)
                                 a066720_list (inits a066720_list)))
-- Reinhard Zumkeller, Nov 19 2013

nmax = 14;
b[1] = 1; F = {1};
For[n = 2, n <= nmax, n++,
For[k = b[n - 1] + 1, True, k++, Fk = Join[{k^2}, Table[b[i]*k, {i, 1, n - 1}]] // Union; If[Fk~Intersection~F == {}, b[n] = k; F = F~Union~Fk; Break[]]]];
Join[{1}, Table[b[k]/b[n], {n, 1, nmax}, {k, 1, n - 1}]] // Flatten // Denominator (* Jean-François Alcover, Aug 23 2022, after Robert Israel in A066720 *)

A076940 Define a mapping for a reduced rational number p/q by f(p/q) = 1 followed by p zeros followed by a 1 followed by q zeros.

Original entry on oeis.org

1010, 10100, 101000, 1001000, 10100000, 100100000, 1000100000, 1010000000, 10010000000, 100010000000, 10000010000000, 10100000000, 1010000, 1000100000000, 100000100000000, 10000000100000000

Offset: 1

Amarnath Murthy, Oct 19 2002

nonn

(p,q) = 1, p = A066657(n) and q = A066658(n).

This gives another proof that rational numbers are countable.

Cf. A066657, A066658.

a(n) = 10^(p+q+1)+ 10^q where p = A066657(n) and q = A066658(n)

cp's OEIS Frontend

A066848 Consider sequence of fractions A066657/A066658 produced by ratios of terms in A066720; let m = smallest integer such that all fractions 1/n, 2/n, ..., (n-1)/n have appeared when we reach A066720(m) = k; sequence gives values of k; set a(n) = -1 if some fraction i/n never appears.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A066849 Consider sequence of fractions A066657/A066658 produced by ratios of terms in A066720; let m = smallest integer such that all fractions 1/n, 2/n, ..., (n-1)/n have appeared when we reach A066720(m) = k; sequence gives values of m; set a(n) = -1 if some fraction i/n never appears.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A076941 a(n) = 2^A066657(n) * 3^A066658(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Extensions

A066720 The greedy rational packing sequence: a(1) = 1; for n > 1, a(n) is smallest number such that the ratios a(i)/a(j) for 1 <= i < j <= n are all distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Extensions

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

A066658 Denominators of rational numbers produced in order by A066720(j)/A066720(i) for i >= 1, 1 <= j

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A076940 Define a mapping for a reduced rational number p/q by f(p/q) = 1 followed by p zeros followed by a 1 followed by q zeros.

Views

Author

Keywords

Comments

Crossrefs

Formula