A287355 Order of largest subset of the positive rationals with neither the sum of numerators nor of denominators exceeding n.

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

Offset

1,3

Links

Table of n, a(n) for n=1..50.

Example

For n = 1, the largest subset is { 1/1 }, so a(1) = 1; for n = 2, the same; for n = 3, largest subsets are { 1/1, 2/1 } and { 1/2, 1/1 }, so a(3) = 2; for n = 4, the largest subset is { 1/2, 1/1, 2/1 }, so a(4) = 3; ...; for n = 16, the largest subset is { 1/4, 1/3, 1/2, 2/3, 1/1, 2/1, 3/1, 4/1 } (or swap 2/3 for 3/2), so a(16)=8, etc.

Prog

(Haskell)
f = go 0 2
  where
    go a r n
      | n >= c             = go (a+t) (r+1) (n-c)
      | n >= r*div n r + m = a + 2*div n r + 1
      | n >= r*div n r + m' + 1 = a + 2*div n r + 1
      | otherwise          = a + 2*div n r
      where
        t  = totient r
        c  = div (r*t) 2
        m  = midnum r
        m' = midnum (r-1)
    midnum r = head [a|a<-[div (r+1) 2..], gcd a r==1]

Crossrefs

Sequence in context: A238516 A282692 A269371 * A194171 A004525 A049206

Adjacent sequences: A287352 A287353 A287354 * A287356 A287357 A287358

Keyword

nonn

Author

Carl Edman, May 23 2017

Status

approved