A099053 -id:A099053 - cp's OEIS frontend

A060274 Hard numbers: a(n) = smallest positive number m with f(m) = n, where f(m) is the smallest number of digits that are needed to construct m using only 1's, 2's and any number of +, -, *, ^ signs, not allowing concatenation of the digits.

1, 3, 5, 7, 13, 21, 41, 91, 269, 419, 921, 2983, 8519, 18859, 53611, 136631, 436341

Offset: 1

Jason Earls, Mar 22 2001

nonn

It seems that to obtain this sequence we need to impose the additional rule that x-y is allowed only when x-y > 0.

This is not correct. See the comment at A099053. - Franklin T. Adams-Watters, Feb 14 2013

			a(11) = 921 because this is the smallest number that requires 11 digits for its expression.

C. A. Pickover, "Wonders of Numbers", Chapter 78, 'Creator Numbers', Oxford University Press, NY, 2001. pp. 187-189, 343-345.
Ken Shirriff, University of California, personal communication.

Sean A. Irvine, Java program (github)
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
Index to sequences related to the complexity of n

The sequence f(n) is given in A099053. Cf. A060273.

Entry revised by Larry Reeves (larryr(AT)acm.org), Apr 26 2001
Entry improved by comments from Tim Peters (tim.one(AT)comcast.net), Nov 14 2004
a(17) from Sean A. Irvine, Nov 06 2022

A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 10, 11, 14, 19, 22, 23, 38, 43, 58, 59, 89, 107, 134, 167, 179, 263, 347, 383, 537, 713, 719, 1103, 1319, 1439, 2099, 2879, 3833, 4283, 5939, 6299, 9059, 12239, 15118, 19079, 23039, 26459, 44879, 49559, 66239, 78839, 98999, 137339

Offset: 1

N. J. A. Sloane, Oct 11 2018

nonn

The shift operation here is also sometimes called successor, see A263283.

Note this complexity measure counts both operands (the ones) and operators (the shifts and multiplications), whereas most of the complexity measures in the crossrefs count only operands. However, in the presence of successor it would not make sense to count only operands, since any number can be expressed with a single occurrence of 1. - Glen Whitney, Oct 06 2021

			1 = 1 has complexity 1
2 = S1 has complexity 2
3 = SS1 has complexity 3
4 = SSS1 has complexity 4
5 = SSSS1 has complexity 5
6 = SSSSS1 has complexity 6
7 = SSSSSS1 has complexity 7
10 = S*SS1SS1 = shift(product of (3 and 3)) has complexity 8
(Note that 8 = *S1SSS1 has complexity 7)
11 = SS*SS1SS1 has complexity 9
14 = SS*SS1SSS1 has complexity 10

Michael S. Branicky, Table of n, a(n) for n = 1..67
Akshunna Shaurya Dogra, Minimal Representations of Natural Numbers Under a Set of Operators, arXiv preprint 1801.01360 [math.HO], Jan 2018.
Index to sequences related to the complexity of n.

Smallest number of complexity n (other definitions): A003037, A005520, A244743, A259466, and A265360.

Other definitions of the complexity of n: A005208, A005245, A025280, and A099053.

def aupton(nn):
    alst, R, allR = [1], {1: {1}}, {1} # R[n] is set reachable using n ops
    for n in range(2, nn+1):
        R[n]  = set(a+1 for a in R[n-1])
        R[n] |= set(a*b for i in range(1, (n+1)//2) for a in R[i] for b in R[n-1-i])
        alst.append(min(R[n] - allR))
        allR |= R[n]
    return alst
print(aupton(49)) # Michael S. Branicky, Oct 06 2021

cp's OEIS Frontend

A060274 Hard numbers: a(n) = smallest positive number m with f(m) = n, where f(m) is the smallest number of digits that are needed to construct m using only 1's, 2's and any number of +, -, *, ^ signs, not allowing concatenation of the digits.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions