cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A091333 Number of 1's required to build n using +, -, *, and parentheses.

Original entry on oeis.org

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

Views

Author

Jens Voß, Dec 30 2003

Keywords

Comments

Consider an alternate complexity measure b(n) which gives the minimum number of 1's necessary to build n using +, -, *, and / (where this additional operation is strict integer division, defined only for n/d where d|n). It turns out that b(n) coincides with a(n) for all n up to 50221174, see A348069. - Glen Whitney, Sep 23 2021
In respect of the previous comment: when creating A362471, where repunits are allowed, we found a difference if we allowed n/d with noninteger (intermediate) results. So, see also A362626. - Peter Munn, Apr 29 2023

Examples

			A091333(23) = 10 because 23 = (1+1+1+1) * (1+1+1) * (1+1) - 1. (Note that 23 is also the smallest index at which A091333 differs from A005245.)

Links

Crossrefs

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091334 (using +, -, *, and ^), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).
Cf. A348069, A362471, A362626.

Programs

  • Python
    from functools import cache
@cache
def f(m):
    if m == 0: return set()
    if m == 1: return {1}
    out = set()
    for j in range(1, m//2+1):
        for x in f(j):
            for y in f(m-j):
                out.update([x + y, x * y])
                if x != y: out.add(abs(x-y))
    return out
def aupton(terms):
    tocover, alst, n = set(range(1, terms+1)), [0 for i in range(terms)], 1
    while len(tocover) > 0:
        for k in f(n) - f(n-1):
            if k <= terms:
                alst[k-1] = n
                tocover.discard(k)
        n += 1
    return alst
print(aupton(77)) # Michael S. Branicky, Sep 28 2021

A348089 Number of 1's required to build n using +, -, *, /, and ^.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 5, 5, 6, 7, 7, 8, 8, 7, 6, 7, 7, 8, 8, 9, 9, 9, 8, 7, 7, 6, 7, 8, 9, 8, 7, 8, 9, 8, 7, 8, 9, 10, 10, 10, 11, 12, 11, 10, 11, 10, 9, 8, 9, 10, 9, 9, 8, 9, 9, 10, 10, 11, 11, 10, 9, 8, 7, 8, 9, 10, 11, 11, 10, 10, 9, 10, 10, 10
Offset: 1

Views

Author

Glen Whitney, Sep 28 2021

Keywords

Comments

Here division is taken to be strict integer division, i.e., j/k is defined only if k|j.
Because of the presence of exponentiation, division reduces the value of a(n) as compared with A091334(n) (which allows the same operations except division) far more often than adding division to A091333 does; see A348069.

Examples

			Because 41 = ((1+1+1)^(1+1+1+1) + 1)/(1+1), and there is no expression with these operators and fewer ones that evaluates to 41, a(41) = 10. Note that 41 is the least n such that a(n) < A091334(n).

Links

Crossrefs

Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091333 (using +, -, and *), A091334 (using +, -, *, and ^), A348262 (using + and ^).
Cf. A348069.

A348083 Number of positive numbers that can be built with n ones using +, -, and *, and require at least n ones.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 6, 6, 8, 13, 18, 21, 35, 45, 61, 90, 121, 162, 241, 323, 450, 638, 865, 1233, 1698, 2349, 3315, 4592, 6382, 8970, 12421, 17351, 24320, 33714, 47218, 65978, 91784, 128177, 179807, 249689, 349549, 489341, 681468, 953769, 1334490, 1860641, 2606043, 3643618, 5086481, 7124229, 9960420
Offset: 1

Views

Author

Glen Whitney, Sep 27 2021

Keywords

Comments

a(n+1)/a(n) appears from the values through n=63 to be oscillating in a narrowing range around 7/5.

Examples

			For n=5, there are two numbers whose minimal expression using 1,+,-, and * uses five ones: 5 = 1+1+1+1+1 and 6 = (1+1)*(1+1+1), so a(5) = 2.
For n=10, there are eight numbers whose minimal expression uses ten ones: 22 = 3(2*3+1)+1, 23 = 2*2*2*3-1, 25 = 5*5, 26 = 3*3*3-1, 28 = 3*3*3+1, 30 = 2*3*5, 32 = 2*2*2*2*2, and 36 = 2*2*3*3. We use numbers k=1..5 in these expressions because each takes k ones to express. Note that n=10 is also the least n for which a(n) differs from A005421(n), which counts the solutions to A005245(k) = n.

Links

  • Glen Whitney, Table of n, a(n) for n = 1..64 (This file produced with the same C code that generated A348069, simply with division eliminated from the loop over operators.)

Crossrefs

Cf. A005421, A091333, A005245.

Programs

  • Python
    from functools import cache
@cache
def f(m):
    if m == 0: return set()
    if m == 1: return {1}
    out = set()
    for j in range(1, m//2+1):
        for x in f(j):
            for y in f(m-j):
                out.update([x + y, x * y])
                if x != y: out.add(abs(x-y))
    return list(out)
def a(n): return len(f(n)) - len(f(n-1))
print([a(n) for n in range(1, 33)]) # Michael S. Branicky, Sep 27 2021

Formula

a(n) = |{k : A091333(k) = n}|.

A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.

Original entry on oeis.org

1860043, 3198487, 4782847, 5580129, 6111571, 9300217, 9566302, 9595461, 9595462, 9654511, 10678027, 12725059, 12843157, 13551745, 14349271, 14614627, 16740391, 17094685, 18334713, 18334714, 19220449, 27900651, 28698178, 28701094, 29494975, 31620739, 32034081, 33484063, 34100797, 35872267, 37998031
Offset: 1

Views

Author

Glen Whitney, Sep 28 2021

Keywords

Comments

Consider an integer complexity measure c(n) which is the number of ones required to build n using +, -, *, and "floor division" which for convenience will be written in this entry (after Python notation) j//k = floor(j/k). In other words, c(n) is defined identically to A091333(n) except that this floor division is also allowed, and identically to the complexity b(n) described in A348069 except that division is extended to all pairs of natural numbers by taking the floor of the quotient. Clearly for all n, c(n) <= b(n) <= A091333(n). This sequence lists the integers k for which c(k) < A091333(k).
Because of the inequality c(n) <= b(n) <= A091333(n), every entry in A348069 will eventually appear in this sequence. For example, the first term of A348069 is 50221174 = (7*3^15)//2, so we have c(50221174) = 53, b(50221174) = 54, and A091333(50221174) = 55.
The extended domain of division means that terms of this sequence are much more frequent than A348069, but it's still quite rare for division to provide more compact expressions for natural numbers (except in the presence of exponentiation, see A348089).

Examples

			The smallest n for which c(n) as defined in the comments is strictly less than A091333(n) is 1860043, because 1860043 = (7*3^12)//2 which requires c(7) + 12*c(3) + c(2) = 6 + 12*3 + 2 = 44 ones to express with these operations, whereas A091333(1860043) = A005245(1860043) = 45 by virtue of the minimal expression 1860043 = 2(2^2*5*7(3^4(3^4+1)+1)+1)+1 requiring 2+2*2+5+6+3*4+3*4+1+1+1+1 = 45 ones. Hence, the first term in this sequence is 1860043.
The next three terms with their respective minimal expressions:
3198487 = (3^9(2^2*3^4+1))//2 [46 ones] = 2*3(3^2(2^2*3*5+1)(2^2*3^5-1)+2)+1 [47 ones] = 2*3(2(7(2^2*3+1)(2^2*3(3^5+1)+1)+1)+1)+1 [48 ones]. Thus n=319487 is the least n for which c(n) < A091333(n) < A005245(n).
4782847 = (3^5(2*3^9-1))//2 [47 ones] = 2*3(2*5(3^2(2^2*3^3(3^4+1)+1)+1)+1)+1 [48 ones]
5580129 = 3*1860043 = 3((7*3^12)//2) [47 ones] = 2^3(3*5*7(3^4(3^4+1)+1)+1)+1 [48 ones]. Note this example critically takes advantage of the fact that * and // are not associative.

Crossrefs

Cf. A253177 and A348069.
Cf. A091333 and A005245 (other integer complexity measures).
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.