cp's OEIS Frontend

A272894 a(n) is the largest natural number k such that the composite number (2n+1) 2^k+1 has a nontrivial divisor of the form h2^s+1 (h odd) with s>k. If such a natural number does not exist, we set a(n)=0.

%I A272894 #22 Jul 25 2017 06:29:47
%S A272894 0,0,0,1,0,2,1,0,1,3,2,0,1,1,2,2,0,4,3,0,2,1,1,2,1,2,3,3,1,1,2,0,2,5,
%T A272894 4,2,3,0,1,1,2,2,1,3,2,3,1,0,1,0,4,4,0,2,3,2,0,1,1,2,3,2,0,3,1,6,5,0,
%U A272894 4,1,2,1,3,1,1,2,3,3,2,2,2,3,0,4,3,4,2,1,1,0,3,0,2,1,3,2,1,1,5,5,2
%N A272894 a(n) is the largest natural number k such that the composite number (2n+1) 2^k+1 has a nontrivial divisor of the form h2^s+1 (h odd) with s>k. If such a natural number does not exist, we set a(n)=0.
%H A272894 Tom Müller, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Mueller/mueller10.html">On the Exponents of Non-Trivial Divisors of Odd Numbers and a Generalization of Proth's Primality Theorem</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.7.
%e A272894 We always have 2^k + 1 < h2^s + 1 if k < s. Thus a(1)=0.
%p A272894 a:= proc(n)
%p A272894 H:=2*n+1:
%p A272894 smax:=floor(evalf(log[2](H))):
%p A272894 R:=0:
%p A272894 for r from 1 to smax-1 do;
%p A272894 for s from r+1 to smax do;
%p A272894 kmax:=floor(evalf(H/2^s)):
%p A272894 for k from 1 to kmax by 2 do;
%p A272894 h:=(H-2^(s-r)*k)/(2^s*k+1):
%p A272894 if h<1 then break fi;
%p A272894 if type(h,integer) and R<r then R:=r fi;
%p A272894 od;
%p A272894 od;
%p A272894 od;
%p A272894 R;
%p A272894 end:
%p A272894 seq(a(n), n=0..100);
%Y A272894 Cf. A272895.
%K A272894 nonn,easy
%O A272894 0,6
%A A272894 _Tom Mueller_, May 09 2016