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.
a(3) = 11, because the maximum of quotients of shortest addition chain length l(k) and the base-2 logarithm of the numbers in the range 2^3 ... 2^4 occurs at k=11. k l(k) log_2(k) l(k)/log_2(k) 8 3 3.0000 1.00000 9 4 3.1699 1.26186 10 4 3.3219 1.20412 11 5 3.4594 1.44532 12 4 3.5849 1.11577 13 5 3.7004 1.35119 14 5 3.8074 1.31325 15 5 3.9069 1.27979 16 4 4.0000 1.00000 a(30)=1886023151 because it produces the largest value of A003313(k)/log_2(k) in the interval 2^30 < k < 2^31, i.e., all other numbers in this range give a smaller quotient than A003313(1886023151) / log_2(1886023151) = 38 / 30.8127 = 1.23325771.
Triangle of the n latest occurrences:
2
4 3
8 6 5
16 12 10 9
32 24 20 18 17
64 48 40 36 34 33
128 96 80 72 68 66 65
256 192 160 144 136 132 130 129
512 384 320 288 272 264 260 258 257
From _Lekraj Beedassy_, Jul 04 2009: (Start)
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)
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))
-- Reinhard Zumkeller, Mar 08 2013
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:
seq(a(n), n=1..100); # Alois P. Heinz, Apr 18 2012
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}}]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)
A005245(n /* start by calling this with the largest needed n */, lim/* see below */) = { local(d); n<6 && return(n); if(n<=#A005245, A005245[n]&return(A005245[n]) /* return memoized result if available */, A005245=vector(n) /* create vector if needed - should better reuse existing data if available */); for(i=1, n-1, A005245[i] || A005245[i]=A005245(i,lim)); /* compute all previous elements */ 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. \\ M. F. Hasler, Jan 30 2008
from functools import lru_cache from itertools import takewhile from sympy import divisors @lru_cache(maxsize=None) def A005245(n): return min(min(A005245(a)+A005245(n-a) for a in range(1,(n>>1)+1)),min((A005245(d)+A005245(n//d) for d in takewhile(lambda d:d*d<=n,divisors(n)) if d>1),default=n)) if n>1 else 1 # Chai Wah Wu, Apr 29 2023
a(19) = 6: 19 - 1 = 18; 18 - 9 = 9; 9 - 3 = 6; 6 - 3 = 3; 3 - 1 = 2; 2 - 1 = 1. That is a total of 6 iterations. - _Jaroslav Krizek_, Jan 28 2010 From _Antti Karttunen_, Apr 04 2020: (Start) We can follow also alternative routes, where we do not always select the largest proper divisor to subtract, for example, from 19 to 1, we could go as: 19-1 = 18; 18-(18/3) = 12; 12-(12/2) = 6; 6-(6/3) = 4; 4-(4/2) = 2; 2-(2/2) = 1, or as 19-1 = 18; 18-(18/3) = 12; 12-(12/3) = 8; 8-(8/2) = 4; 4-(4/2) = 2; 2-(2/2) = 1, both of which also have exactly 6 iterations. (End)
import Data.List (genericIndex)
a064097 n = genericIndex a064097_list (n-1)
a064097_list = 0 : f 2 where
f x | x == spf = 1 + a064097 (spf - 1) : f (x + 1)
| otherwise = a064097 spf + a064097 (x `div` spf) : f (x + 1)
where spf = a020639 x
-- Reinhard Zumkeller, Mar 08 2013
a:= proc(n) option remember;
add((1+a(i[1]-1))*i[2], i=ifactors(n)[2])
end:
seq(a(n), n=1..120); # Alois P. Heinz, Apr 26 2019
# alternative which can be even used outside this entry
A064097 := proc(n)
option remember ;
add((1+procname(i[1]-1))*i[2], i=ifactors(n)[2]) ;
end proc:
seq(A064097(n),n=1..100) ; # R. J. Mathar, Aug 07 2022
quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &; quasiLog /@ Range[1024] (* Terentyev Oleg, Jul 17 2011 *) fi[n_] := Flatten[ Table[#[[1]], {#[[2]]}] & /@ FactorInteger@ n]; a[1] = 0; a[n_] := If[ PrimeQ@ n, a[n - 1] + 1, Plus @@ (a@# & /@ fi@ n)]; Array[a, 105] (* Robert G. Wilson v, Jul 17 2013 *) a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &] - 1; Array[a, 100] (* or *) a[n_] := a[n - n/FactorInteger[n][[1, 1]]] +1; a[1] = 0; Array[a, 100] (* Robert G. Wilson v, Mar 03 2020 *)
NN=200; an=vector(NN); a(n)=an[n]; for(n=2,NN,an[n]=if(isprime(n),1+a(n-1), sumdiv(n,p, if(isprime(p),a(p)*valuation(n,p))))); for(n=1,100,print1(a(n)", "))
a(n)=if(isprime(n), return(a(n-1)+1)); if(n==1, return(0)); my(f=factor(n)); apply(a,f[,1])~ * f[,2] \\ Charles R Greathouse IV, May 10 2016
(define (A064097 n) (if (= 1 n) 0 (+ 1 (A064097 (A060681 n))))) ;; After Jaroslav Krizek's Jan 28 2010 formula. (define (A060681 n) (- n (A032742 n))) ;; See also code under A032742. ;; Antti Karttunen, Aug 23 2017
Comments