A333789 - OEIS

%I #20 Dec 20 2024 20:43:12

%S 119,143,187,209,221,238,239,286,319,357,374,407,418,419,429,442,443,

%T 451,476,478,479,561,572,595,627,638,663,667,671,703,713,714,715,717,

%U 748,779,803,814,833,836,838,839,851,858,859,884,886,887,902,935,943,952,953,956,957,958,979,989,1001,1045,1067,1071,1073,1105,1111,1122

%N Numbers k for which A333790(k) < A073934(k).

%C Numbers n for which the {smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k} cannot be obtained by always selecting the smallest prime factor of k (A020639). See the example in A333790 how that simple heuristic fails when starting from k=119.

%H Antti Karttunen, <a href="/A333789/b333789.txt">Table of n, a(n) for n = 1..36576; all terms <= 2^17</a>

%t Block[{a, b, nn = 1122}, a = Min@ Map[Total, #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, nn]; b = Array[If[# == 1, 1, Total@ NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, nn]; Select[Range@ nn, a[[#]] < b[[#]] &]] (* _Michael De Vlieger_, Apr 15 2020 *)

%o (PARI)

%o search_up_to = 2^17;

%o A333790list(up_to) = { my(v=vector(up_to)); v[1] = 1; for(n=2, up_to, v[n] = n+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };

%o v333790 = A333790list(search_up_to);

%o A333790(n) = v333790[n];

%o A073934(n) = if(1==n,n,n + A073934(n-(n/vecmin(factor(n)[,1]))));

%o isA333789(n) = (A073934(n)!=A333790(n));

%Y Cf. A020639, A060681, A073934, A333790.

%K nonn,changed

%O 1,1

%A _Antti Karttunen_, Apr 12 2020