cp's OEIS Frontend

A276770 a(n) is the number of runs of an algorithm. Set b_0 = n, if prime, stop; else, set c_0 = largest divisor of n (!=n); set b_1 = c_0 + b_0/c_0. Run with b_1.

%I A276770 #21 Oct 04 2016 13:33:53
%S A276770 0,1,0,2,2,1,0,3,0,3,3,2,0,1,0,4,2,1,0,4,2,4,4,3,0,1,0,2,4,1,4,5,0,3,
%T A276770 3,2,0,1,0,5,2,3,0,5,4,5,5,4,0,1,3,2,2,1,0,3,0,5,5,2,2,5,0,6,5,1,0,4,
%U A276770 0,4,4,3,2,1,0,2,2,1,0,6,2,3,3,4,0,1,5,6,2,5,5,6,0,6,6,5,0,1,0,2,4
%N A276770 a(n) is the number of runs of an algorithm. Set b_0 = n, if prime, stop; else, set c_0 = largest divisor of n (!=n); set b_1 = c_0 + b_0/c_0. Run with b_1.
%C A276770 a(4) -> infinity. For any other n >= 2, a(n) is finite, however cases n = 2,3 are trivial, so the offset is 5.
%C A276770 For large n: Sum_{k=5..n} a(k) ~ n*log(n)/2 (conjectured).
%H A276770 Yuriy Sibirmovsky, <a href="/A276770/b276770.txt">Table of n, a(n) for n = 5..1000</a>
%H A276770 Yuriy Sibirmovsky, <a href="/A276770/a276770.png">Plot of sum_{k=5..n} a(k) for n = 5..20000</a>
%e A276770 For n=14: b_0 = 14, not prime. c_0 = 7. b_1 = 7 + 2 = 9. 9 is not prime.
%e A276770 In short: 14 -> {7,2} -> 9 -> {3,3} -> 6 -> {3,2} -> 5. Number of runs a(14) = 3.
%t A276770 Nm=100;
%t A276770 a=Table[0,{n,1,Nm}];
%t A276770 Do[b0=n;
%t A276770 j=0;
%t A276770 While[PrimeQ[b0]==False,c=Reverse[Divisors[b0]];
%t A276770 b1=c[[2]]+b0/c[[2]];
%t A276770 b0=b1;j++];
%t A276770 a[[n]]=j,{n,5,Nm}];
%t A276770 Table[a[[k]],{k,5,Nm}]
%o A276770 (PARI) stop(n) = (n<=1) || isprime(n);
%o A276770 a(n) = {b = n; nb = 0; while (! stop(b), d = divisors(b); c = d[#d-1]; b = c + b/c; nb++;); nb;} \\ _Michel Marcus_, Sep 19 2016
%Y A276770 Cf. A000040, A276771.
%K A276770 nonn
%O A276770 5,4
%A A276770 _Yuriy Sibirmovsky_, Sep 17 2016