|
|
A005520
|
|
Smallest number of complexity n: smallest number requiring n 1's to build using + and *.
(Formerly M0523)
|
|
31
|
|
|
1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, 59, 89, 107, 167, 179, 263, 347, 467, 683, 719, 1223, 1438, 1439, 2879, 3767, 4283, 6299, 10079, 11807, 15287, 21599, 33599, 45197, 56039, 81647, 98999, 163259, 203999, 241883, 371447, 540539, 590399, 907199
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Ed Pegg Jr, www.mathpuzzle.com, Apr 10 2001, notes that all the new terms are -1 mod 120. - That is, this holds at least for all terms from a(45) = 590399 up to the highest known term a(89) given in the b-file at the end of 2015. Comment clarified by Antti Karttunen, Dec 14 2015
After 1438 = 2 * 719, all elements through 8206559 are primes. Equivalently, except for a(4) = 4, a(7) = 10, a(10) = 22 and a(25) = 1438, we have a(1) through a(53) are all primes. - Jonathan Vos Post, Apr 07 2006
Previous observations (primes with property -1 mod 120) still hold. - Martins Opmanis, Oct 16 2009
The prime 353942783 = A189125(1) = 2*3 + (1 + 2^2*3^2)*(2 + 3^4(1 + 2*3^10)) is the smallest counterexample to Guy's first hypothesis on integer complexity. - Jonathan Vos Post, Mar 30 2012
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems in Number Theory, Sec. F26 (related material).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
EXAMPLE
|
Examples from Piotr Fabian:
1 = 1, 1 "one": first 1, a(1) = 1
2 = 1+1, 2 "ones": first 2, a(2) = 2
3 = 1+1+1, 3 "ones": first 3, a(3) = 3
4 = 1+1+1+1, 4 "ones": first 4, a(4) = 4
5 = 1+1+1+1+1, 5 "ones": first 5, a(5) = 5
6 = (1+1)*(1+1+1), 5 "ones"
7 = 1+((1+1)*(1+1+1)), 6 "ones": first 6, a(6) = 7
8 = (1+1)*(1+1+1+1), 6 "ones"
9 = (1+1+1)*(1+1+1), 6 "ones"
10 = 1+((1+1+1)*(1+1+1)), 7 "ones": first 7, a(7) = 10
11 = 1+(1+(1+1+1)*(1+1+1)), 8 "ones": first 8, a(8) = 11
12 = (1+1)*((1+1)*(1+1+1)), 7 "ones"
|
|
MAPLE
|
N:= 100000: # to get all terms <= N
R:= Vector(N):
R[1]:= 1: A[1]:= 1:
for n from 2 to N do
inds:= [seq(n-i, i=1..floor(n/2))];
m:= min(R[1..floor(n/2)] + R[inds]);
for d in select(`<=`, numtheory:-divisors(n), floor(sqrt(n))) minus {1} do
m:= min(m, R[d]+R[n/d])
od;
R[n]:= m;
if not assigned(A[m]) then A[m]:= n fi;
od:
|
|
MATHEMATICA
|
nn = 10000;
R = Table[0, nn];
R[[1]] = 1; Clear[A]; A[1] = 1;
For[n = 2, n <= nn, n++,
inds = Table[n-i, {i, 1, n/2}];
m = Min[R[[1 ;; Floor[n/2]]] + R[[inds]]];
Do[
m = Min[m, R[[d]] + R[[n/d]]], {d,
Select[Rest[Divisors[n]], # <= Sqrt[n]&]}
];
R[[n]] = m;
If[!IntegerQ[A[m]], A[m] = n];
];
|
|
PROG
|
See the Python program by Tim Peters at A005421.
(MATLAB)
N = 10^6;
fact = cell(1, N);
for n = 2:sqrt(N)
for m = [n^2:n:N]
fact{m} = [fact{m}, n];
end
end
R = zeros(1, N);
R(1) = 1;
A(1) = 1;
mmax = 1;
for n = 2:N
m = min(R(1:floor(n/2)) + R([n-1:-1:ceil(n/2)]));
if numel(fact{n}) > 0
m = min(m, min(R(fact{n}) + R(n ./ fact{n})));
end
R(n) = m;
if m > mmax
A(m) = n;
mmax = m;
elseif A(m) == 0
A(m) = n;
end
end
(Python)
def aupton(nn):
alst, R = [1], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
for n in range(1, nn):
R[n] = set(a+b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
R[n] |= set(a*b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
alst.append(min(R[n] - R[n-1]))
return alst
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Extended to terms a(40)=163259 and a(41)=203999 by John W. Layman, Nov 03 1999
Further terms from Piotr Fabian (PCF(AT)who.net), Mar 30 2001
|
|
STATUS
|
approved
|
|
|
|