login
Least positive integer not representable using exactly n 9's and the operations +-*/().
0

%I #17 Aug 03 2023 10:45:58

%S 1,2,1,4,13,22,33,103,195,381,934,1858,3747,9166,31279

%N Least positive integer not representable using exactly n 9's and the operations +-*/().

%C This sequence allows fractions as intermediate results; else, a(9) would equal 138. - _Michael S. Branicky_, Feb 08 2023

%H Joe K. Crump, <a href="http://web.archive.org/web/20070630090158/http://www.immortaltheory.com/NumberTheory/nines.htm">The 9 Nines</a>

%H <a href="/index/Fo#4x4">Index entries for similar sequences</a>

%e a(4)=4 because 4 cannot be expressed with exactly 4 nines and the operations +-*/(). E.g. 1 = 9/9+9-9, 2 = 9/9+9/9, 3 = (9+9+9)/9, but 4 has no such representation.

%e 138 = (((9 - (9 / ((9 + 9) + 9))) * (9 + 9)) - 9) - 9.

%e 265 = ((((9 - (9 / (9 + 9))) + 9) + 9) * ((9 * 9) + 9)) / 9.

%o (Python)

%o from fractions import Fraction

%o from functools import lru_cache

%o def a(n):

%o @lru_cache()

%o def f(m):

%o if m == 1: return {9}

%o out = set()

%o for j in range(1, m//2+1):

%o for x in f(j):

%o for y in f(m-j):

%o out.update([x + y, x - y, y - x, x * y])

%o if y: out.add(Fraction(x, y))

%o if x: out.add(Fraction(y, x))

%o return out

%o k, s = 1, f(n)

%o while k in s: k += 1

%o return k

%o print([a(n) for n in range(1, 10)]) # _Michael S. Branicky_, Feb 08 2023

%K more,nonn

%O 1,2

%A Joe K. Crump (joecr(AT)carolina.rr.com), Dec 24 2001

%E Corrected by Leonhard Vogt (leonhard.vogt(AT)gmx.ch), Jan 09 2006

%E a(11)-a(13) from _Michael S. Branicky_, Feb 08 2023

%E a(14)-a(15) from _Michael S. Branicky_, Aug 03 2023