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

%I #49 Dec 03 2015 16:29:50

%S 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 61,63,64,66,67,70,73,75,76,79,81,82,84,85,88,90,91,93,94,97,100,102,

%U 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 Positive integers n that can be expressed as the quotient of two elements of A005836.

%C 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 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 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 n is in the sequence if and only if 3*n is in the sequence. - _Robert Israel_, Dec 03 2015

%H 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 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 F:= proc(N)

%p option remember;

%p uses GraphTheory;

%p local L,G,a,k;

%p if N mod 3 = 0 then procname(N/3)

%p elif N mod 3 = 2 then return false

%p fi;

%p k:= ceil(log[3](2*N/3));

%p if N < (2/3)*3^k then return false fi;

%p for a from 1 to N-1 do

%p L[a]:= {3*a,3*a+1}

%p od:

%p for a from N to 2*N-1 do

%p L[a]:= subs(0=3*N,{3*(a-N),3*(a-N)+1});

%p od:

%p for a from 2*N to 3*N do

%p L[a]:= {};

%p od:

%p L[3*N+1]:= remove(t -> has(convert(t,base,3),2), {$1..3*N-1}):

%p G:= Digraph(3*N+1,[seq(L[a],a=1..3*N+1)]);

%p try

%p ShortestPath(G,3*N+1,3*N);

%p catch "no path from": return false;

%p end try;

%p true

%p end proc:

%p select(F, [$1..1000]); # _Robert Israel_, Dec 03 2015

%Y Cf. A005836.

%K nonn,base

%O 1,2

%A _Jeffrey Shallit_, Dec 02 2015