Integer Complexity

Author

Eric W. Weisstein
April 19, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/IntegerComplexity.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/IntegerComplexity.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

Code based on
Ed Pegg, Jr.
http://library.wolfram.com/infocenter/MathSource/5175/

Code

Complexity[A_]:=Join[A,
{Complement[Union[Flatten[
MapIndexed[Outer[If[#1>#2,Plus[##],Times[##]]&,A[[First[#2]]],A[[-First[#2]]]]&,A]
]],
Union[Flatten[A]]]
}]
ComplexitySequence[n_]:=Nest[Complexity,List/@{1,2},n]

Examples

ComplexitySequence[10]

c=ComplexitySequence[30];//Timing

c=ComplexitySequence[35];//Timing

c=ComplexitySequence[40];//Timing

c=ComplexitySequence[45];//Timing

c=ComplexitySequence[46];//Timing

MaxMemoryUsed[]/10.^6 Megabyte

c=ComplexitySequence[47];//Timing

Min/@c

First[Complement[Range[Max[#]],#]&[Sort[Flatten[c]]]]//Timing

Length[ic=Last/@Sort[Flatten[MapIndexed[Transpose[{#1,Table[#2[[1]],{Length[#1]}]}]&,c],1]]]//Timing

Take[ic,100]