|
|
A005245
|
|
The (Mahler-Popken) complexity of n: minimal number of 1's required to build n using + and *.
(Formerly M0457)
|
|
55
|
|
|
1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 11, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 13, 11, 12, 12, 12, 12, 13, 11, 12, 12, 12, 13, 14, 12, 13, 13, 12, 12, 13, 13, 14, 13, 14, 13, 14, 12, 13, 13, 13, 13, 14, 13, 14
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications and parentheses. This does not allow juxtaposition of 1's to form larger integers, so for example, 2 = 1+1 has complexity 2, but 11 does not ("pasting together" two 1's is not an allowed operation).
The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.
Guy asks if a(p) = a(p-1) + 1 for prime p. Martin Fuller found the least counterexample p = 353942783 in 2008, see Fuller link. - Charles R Greathouse IV, Oct 04 2012
It appears that this sequence is lower than A348262 {1,+,^} only a finite number of times. - Gordon Hamilton and Brad Ballinger, May 23 2022
The second Altman links proves that {a(n) - 3*log_3(n)} is a well-ordered subset of the reals whose intersection with [0,k) has order type omega^k for each positive integer k, so this set itself has order type omega^omega. - Jianing Song, Apr 13 2024
|
|
REFERENCES
|
M. Criton, "Les uns de Germain", Problem No. 4, pp. 13 ; 68 in '7 x 7 Enigmes Et Défis Mathématiques pour tous', vol. 25, Editions POLE, Paris 2001.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.
K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (Dutch: On a maximum problem in arithmetic), Nieuw Arch. Wiskunde, (3) 1 (1953), pp. 1-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Katherine Cordwell, Alyssa Epstein, Anand Hemmady, Steven J. Miller, Eyvindur A. Palsson, Aaditya Sharma, Stefan Steinerberger and Yen Nhi Truong Vu, On algorithms to calculate integer complexity, arXiv:1706.08424 [math.NT], 2017.
|
|
FORMULA
|
It is known that a(n) <= A061373(n) but I think 0 <= A061373(n) - a(n) <= 1 also holds. - Benoit Cloitre, Nov 23 2003 [That's false: the numbers {46, 235, 649, 1081, 7849, 31669, 61993} require {1, 2, 3, 4, 5, 6, 7} fewer 1's in A005245 than in A061373. - Ed Pegg Jr, Apr 13 2004]
It is known from the work of Selfridge and Coppersmith that 3 log_3 n <= a(n) <= 3 log_2 n = 4.754... log_3 n for all n > 1. [Guy, Unsolved Problems in Number Theory, Sect. F26.] - Charles R Greathouse IV, Apr 19 2012 [Comment revised by N. J. A. Sloane, Jul 17 2016]
Zelinsky (2022) improves the upper bound to a(n) <= A*log n where A = 41/log(55296) = 3.754422.... This compares to the constant 2.7307176... of the lower bound. - Charles R Greathouse IV, Dec 11 2022
|
|
EXAMPLE
|
n.........minimal expression........ a(n) = number of 1's
1..................1...................1
2.................1+1..................2
3................1+1+1.................3
4.............(1+1)*(1+1)..............4
5............(1+1)*(1+1)+1.............5
6............(1+1)*(1+1+1).............5
7...........(1+1)*(1+1+1)+1............6
8..........(1+1)*(1+1)*(1+1)...........6
9...........(1+1+1)*(1+1+1)............6
10..........(1+1+1)*(1+1+1)+1...........7
11.........(1+1+1)*(1+1+1)+1+1..........8
12.........(1+1)*(1+1)*(1+1+1)..........7
13........(1+1)*(1+1)*(1+1+1)+1.........8
14.......{(1+1)*(1+1+1)+1}*(1+1)........8
15.......{(1+1)*(1+1)+1}*(1+1+1)........8
16.......(1+1)*(1+1)*(1+1)*(1+1)........8
17......(1+1)*(1+1)*(1+1)*(1+1)+1.......9
18........(1+1)*(1+1+1)*(1+1+1).........8
19.......(1+1)*(1+1+1)*(1+1+1)+1........9
20......{(1+1+1)*(1+1+1)+1}*(1+1).......9
21......{(1+1)*(1+1+1)+1}*(1+1+1).......9
22.....{(1+1)*(1+1+1)+1}*(1+1+1)+1.....10
23....{(1+1)*(1+1+1)+1}*(1+1+1)+1+1....11
24......(1+1)*(1+1)*(1+1)*(1+1+1).......9
25.....(1+1)*(1+1)*(1+1)*(1+1+1)+1.....10
26....{(1+1)*(1+1)*(1+1+1)+1}*(1+1)....10
27.......(1+1+1)*(1+1+1)*(1+1+1)........9
28......(1+1+1)*(1+1+1)*(1+1+1)+1......10
29.....(1+1+1)*(1+1+1)*(1+1+1)+1+1.....11
30.....{(1+1+1)*(1+1+1)+1}*(1+1+1).....10
31....{(1+1+1)*(1+1+1)+1}*(1+1+1)+1....11
32....(1+1)*(1+1)*(1+1)*(1+1)*(1+1)....10
33...(1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1...11
34..{(1+1)*(1+1)*(1+1)*(1+1)+1}*(1+1)..11
.........................................
(End)
|
|
MAPLE
|
with(numtheory):
a:= proc(n) option remember;
`if`(n=1, 1, min(seq(a(i)+a(n-i), i=1..n/2),
seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
end:
|
|
MATHEMATICA
|
a[n_] := a[n] = If[n == 1, 1,
Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~
Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]];
|
|
PROG
|
(PARI) A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n);
A005245=vector(n) /* create vector if needed - should better reuse existing data if available */);
A005245[n]=min( vecmin(vector(min(n\2, if(lim>0, lim, n)), k, A005245[k]+A005245[n-k])) /* additive possibilities - if lim>0 is given, consider a(k)+a(n-k) only for k<=lim - we know it is save to use lim=1 up to n=2e7 */, if( isprime(n), n, vecmin(vector((-1+#d=divisors(n))\2, i, A005245[d[i+1]]+A005245[d[ #d-i]]))/* multiplicative possibilities */))}
\\ See also the Python program by Tim Peters at A005421.
(Haskell)
import Data.List (genericIndex)
a005245 n = a005245_list `genericIndex` (n-1)
a005245_list = 1 : f 2 [1] where
f x ys = y : f (x + 1) (y : ys) where
y = minimum $
(zipWith (+) (take (x `div` 2) ys) (reverse ys)) ++
(zipWith (+) (map a005245 $ tail $ a161906_row x)
(map a005245 $ reverse $ init $ a161908_row x))
(Python)
from functools import lru_cache
from itertools import takewhile
from sympy import divisors
@lru_cache(maxsize=None)
|
|
CROSSREFS
|
Cf. A000792 (largest integer of given complexity), A003313, A076142, A076091, A061373, A005421, A064097, A005520, A025280, A003037, A161906, A161908, A244743.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|