cp's OEIS Frontend

A263488 Positive integers n that can be expressed as the quotient of two elements of A005836.

%I A263488 #49 Dec 03 2015 16:29:50
%S A263488 1,3,4,7,9,10,12,13,19,21,22,25,27,28,30,31,34,36,37,39,40,55,57,58,
%T A263488 61,63,64,66,67,70,73,75,76,79,81,82,84,85,88,90,91,93,94,97,100,102,
%U A263488 103,106,108,109,111,112,115,117,118,120,121,163,165,166,169,171,172,174,175,178,181,183,184,187,189,190,192,193,196
%N A263488 Positive integers n that can be expressed as the quotient of two elements of A005836.
%C A263488 For each n, a proof of the existence or nonexistence of such a representation can be constructed effectively, by building a finite-state transducer that multiplies by n, and then searching for a path in the corresponding directed graph whose inputs and outputs are labeled only with 0's and 1's. This was used to show, for example, that 529, 592, 601, 616, 5368, and 50281 have no such representation.
%C A263488 It is not hard to show that every element of this sequence lies in an interval bounded by (2/3)*3^n and (3/2)*3^n for some n >= 0. However, not all elements of these intervals have a representation.
%C A263488 It is also not hard to see that if the last nonzero digit of n in base 3 is a 2, then n is not an element of the sequence.
%C A263488 n is in the sequence if and only if 3*n is in the sequence. - _Robert Israel_, Dec 03 2015
%H A263488 Jeffrey Shallit and Robert Israel, <a href="/A263488/b263488.txt">Table of n, a(n) for n = 1..1000</a> (n = 1..399 from Jeffrey Shallit)
%e A263488 7 is in the sequence because it can be expressed as 28/4, and in base 3 28 is 1001 and 4 is 11.
%p A263488 F:= proc(N)
%p A263488   option remember;
%p A263488   uses GraphTheory;
%p A263488   local L,G,a,k;
%p A263488   if N mod 3 = 0 then procname(N/3)
%p A263488   elif N mod 3 = 2 then return false
%p A263488   fi;
%p A263488   k:=  ceil(log[3](2*N/3));
%p A263488   if N < (2/3)*3^k then return false fi;
%p A263488   for a from 1 to N-1 do
%p A263488      L[a]:= {3*a,3*a+1}
%p A263488   od:
%p A263488   for a from N to 2*N-1 do
%p A263488      L[a]:= subs(0=3*N,{3*(a-N),3*(a-N)+1});
%p A263488   od:
%p A263488   for a from 2*N to 3*N do
%p A263488      L[a]:= {};
%p A263488   od:
%p A263488   L[3*N+1]:= remove(t -> has(convert(t,base,3),2), {$1..3*N-1}):
%p A263488   G:= Digraph(3*N+1,[seq(L[a],a=1..3*N+1)]);
%p A263488   try
%p A263488     ShortestPath(G,3*N+1,3*N);
%p A263488   catch "no path from": return false;
%p A263488   end try;
%p A263488   true
%p A263488 end proc:
%p A263488 select(F, [$1..1000]); # _Robert Israel_, Dec 03 2015
%Y A263488 Cf. A005836.
%K A263488 nonn,base
%O A263488 1,2
%A A263488 _Jeffrey Shallit_, Dec 02 2015