login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j). 9

%I

%S 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,

%T 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,

%U 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

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

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

%C Sum(A226314(n,k)/A054531(n,k): 1<=k<=n) = A226555(n)/A040001(n). - _Reinhard Zumkeller_, Jun 10 2013

%H Reinhard Zumkeller, <a href="/A226314/b226314.txt">Rows n = 1..120 of triangle, flattened</a>

%H Lance Fortnow, <a href="http://blog.computationalcomplexity.org/2004/03/counting-rationals-quickly.html">Counting the Rationals Quickly</a>, Computational Complexity Weblog, Monday, March 01, 2004.

%H Yoram Sagher, <a href="http://www.jstor.org/stable/2324846">Counting the rationals</a>, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

%e Triangle begins:

%e [1]

%e [1, 2]

%e [1, 2, 3]

%e [1, 3, 3, 4]

%e [1, 2, 3, 4, 5]

%e [1, 4, 5, 5, 5, 6]

%e [1, 2, 3, 4, 5, 6, 7]

%e [1, 5, 3, 7, 5, 7, 7, 8]

%e [1, 2, 7, 4, 5, 8, 7, 8, 9]

%e [1, 6, 3, 7, 9, 8, 7, 9, 9, 10]

%e ...

%e The resulting triangle of fractions begins:

%e 1,

%e 1/2, 2,

%e 1/3, 2/3, 3,

%e 1/4, 3/2, 3/4, 4,

%e 1/5, 2/5, 3/5, 4/5, 5,

%e ...

%p f:=(i,j) -> j+(i-j)/gcd(i,j);

%p g:=n->[seq(f(i,n),i=1..n)];

%p for n from 1 to 20 do lprint(g(n)); od:

%o (Haskell)

%o a226314 n k = n - (n - k) `div` gcd n k

%o a226314_row n = a226314_tabl !! (n-1)

%o a226314_tabl = map f $ tail a002262_tabl where

%o f us'@(_:us) = map (v -) $ zipWith div vs (map (gcd v) us)

%o where (v:vs) = reverse us'

%o -- _Reinhard Zumkeller_, Jun 10 2013

%Y Cf. A002262.

%Y Cf. A037161, A037162, A066657, A066658.

%K nonn,frac,tabl

%O 1,3

%A _N. J. A. Sloane_, Jun 09 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 12:18 EDT 2020. Contains 335448 sequences. (Running on oeis4.)