cp's OEIS Frontend

A177803 The number of lines in the analog of Pratt primality certificate for the n-th semiprime.

%I A177803 #17 Nov 20 2020 05:35:31
%S A177803 1,2,1,2,1,2,3,4,1,3,1,2,3,2,1,4,1,5,6,7,1,3,4,5,3,3,1,7,1,2,3,4,5,5,
%T A177803 1,2,3,5,1,8,1,8,5,6,1,3,4,7,8,6,1,4,5,3,4,5,1,8,1,2,8,2,3,10,1,5,6,9,
%U A177803 1,5,1,2,6,3,4,8,1,5,3,4,1,9,10,11,12,8,1,9,10,7,8,9,10,3,1,5,5
%N A177803 The number of lines in the analog of Pratt primality certificate for the n-th semiprime.
%H A177803 Alois P. Heinz, <a href="/A177803/b177803.txt">Table of n, a(n) for n = 4..1000</a>
%F A177803 a(4) = 1; a(n) = 1 + Sum a(k), k semiprime, k | n-1.
%e A177803 a (5) = 2 = 1 + a(4) because 4 | (5-1) and 4 = 2*2 is a semiprime.
%e A177803 a (6) = 1 because there is no semiprime that divides (6-1) = 5, a prime.
%e A177803 a (7) = 2 = 1 + a(6) = 1+1 because 6 | (7-1) and 6 = 2*3 is a semiprime.
%e A177803 a (8) = 1 because there is no semiprime that divides (8-1) = 7, a prime.
%e A177803 a (9) = 2 = 1 + a(4) = 1+1 because 4 | (9-1).
%e A177803 a(10) = 3 = 1 + a(9) = 1+2 because 9 | (10-1) and 9 is a semiprime.
%e A177803 a(11) = 4 = 1 + a(10) = 1+3 because 10 | (11-1) and 10 = 2*5 is a semiprime.
%e A177803 a(12) = 1 because there is no semiprime that divides (12-1) = 11, a prime.
%e A177803 a(13) = 3 = 1 + a(4) + a(6) = 1+1+1 because both 4 and 6 divide into (13-1) = 12 and are semiprimes.
%e A177803 a(14) = 1 because there is no semiprime that divides (14-1) = 13, a prime.
%e A177803 a(15) = 2 = 1 + a(14) = 1+1 because 14 | (15-1).
%e A177803 a(16) = 3 = 1 + a(15) = 1+2 because 15=3*5 is the only semiprime which divides 16-1.
%e A177803 a(17) = 2 = 1 + a(4) = 1+1 because 4 | (17-1) and 4 is the only such semiprime.
%p A177803 a:= proc(n) option remember; 1 +add (`if` (not isprime(k) and add (i[2], i=ifactors(k)[2])=2 and irem (n-1, k)=0, a(k), 0), k=4..n-1) end: seq (a(n), n=4..100);  # _Alois P. Heinz_, Dec 12 2010
%t A177803 a[n_] := a[n] = 1 + Sum[If[!PrimeQ[k] && Total@FactorInteger[k][[All, 2]] == 2 && Mod[n - 1, k] == 0, a[k], 0], {k, 4, n - 1}];
%t A177803 a /@ Range[4, 100] (* _Jean-François Alcover_, Nov 20 2020, after _Alois P. Heinz_ *)
%Y A177803 Cf. A001358, A037202.
%K A177803 nonn,easy
%O A177803 4,2
%A A177803 _Jonathan Vos Post_, Dec 12 2010
%E A177803 More terms from _Alois P. Heinz_, Dec 12 2010