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

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

Author

N. J. A. Sloane, Jun 09 2013

Keywords

• nonn
• frac
• tabl

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A002262.

Cf. A037161, A037162, A066657, A066658.

Programs

Haskell

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

Maple

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: