cp's OEIS Frontend

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

%I A276771 #20 Oct 04 2016 13:34:29
%S A276771 0,0,0,1,0,1,0,1,1,1,0,2,0,1,1,2,0,1,0,2,2,2,0,2,1,1,2,3,0,1,0,2,2,2,
%T A276771 1,3,0,1,2,2,0,1,0,3,3,3,0,3,1,1,2,3,0,2,2,2,3,3,0,4,0,1,2,2,2,1,0,3,
%U A276771 3,3,0,3,0,2,3,4,2,1,0,2,3,3,0,3,3,1,2,2,0,1,2,4,4,4,2,4,0,1,2,4
%N A276771 a(n) is the number of runs of an algorithm. Set b_0 = n, if prime or 1 or 0, stop; else, set c_0 = largest divisor of n (!=n); set b_1 = c_0 - b_0/c_0. Run with b_1.
%C A276771 For large n: Sum_{k=1..n} a(k) ~ n*log(n)/2 - n/2 (conjectured).
%H A276771 Yuriy Sibirmovsky, <a href="/A276771/b276771.txt">Table of n, a(n) for n = 1..1000</a>
%H A276771 Yuriy Sibirmovsky, <a href="/A276771/a276771.png">Plot of sum_{k=1..n} a(k) for n = 1..20000</a>
%e A276771 For n=14: b_0 = 14, not prime or 1 or 0. c_0 = 7. b_1 = 7 - 2 = 5. 5 is prime.
%e A276771 In short: 14 -> {7,2} -> 5. Number of runs a(14) = 1.
%t A276771 Nm=100;
%t A276771 a=Table[0,{n,1,Nm}];
%t A276771 Do[b0=n;
%t A276771 j=0;
%t A276771 While[PrimeQ[b0]==False&&b0!=1&&b0!=0,c=Reverse[Divisors[b0]];
%t A276771 b1=c[[2]]-b0/c[[2]];
%t A276771 b0=b1;j++];
%t A276771 a[[n]]=j,{n,1,Nm}];
%t A276771 a
%o A276771 (PARI) stop(n) = (n<=1) || isprime(n);
%o A276771 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 A276771 Cf. A000040, A276770.
%K A276771 nonn
%O A276771 1,12
%A A276771 _Yuriy Sibirmovsky_, Sep 17 2016