cp's OEIS Frontend

A333789 Numbers k for which A333790(k) < A073934(k).

%I A333789 #20 Dec 20 2024 20:43:12
%S A333789 119,143,187,209,221,238,239,286,319,357,374,407,418,419,429,442,443,
%T A333789 451,476,478,479,561,572,595,627,638,663,667,671,703,713,714,715,717,
%U A333789 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 A333789 Numbers k for which A333790(k) < A073934(k).
%C A333789 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 A333789 Antti Karttunen, <a href="/A333789/b333789.txt">Table of n, a(n) for n = 1..36576; all terms <= 2^17</a>
%t A333789 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 A333789 (PARI)
%o A333789 search_up_to = 2^17;
%o A333789 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 A333789 v333790 = A333790list(search_up_to);
%o A333789 A333790(n) = v333790[n];
%o A333789 A073934(n) = if(1==n,n,n + A073934(n-(n/vecmin(factor(n)[,1]))));
%o A333789 isA333789(n) = (A073934(n)!=A333790(n));
%Y A333789 Cf. A020639, A060681, A073934, A333790.
%K A333789 nonn
%O A333789 1,1
%A A333789 _Antti Karttunen_, Apr 12 2020