OFFSET
1,2
COMMENTS
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.
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.
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.
n is in the sequence if and only if 3*n is in the sequence. - Robert Israel, Dec 03 2015
LINKS
Jeffrey Shallit and Robert Israel, Table of n, a(n) for n = 1..1000 (n = 1..399 from Jeffrey Shallit)
EXAMPLE
7 is in the sequence because it can be expressed as 28/4, and in base 3 28 is 1001 and 4 is 11.
MAPLE
F:= proc(N)
option remember;
uses GraphTheory;
local L, G, a, k;
if N mod 3 = 0 then procname(N/3)
elif N mod 3 = 2 then return false
fi;
k:= ceil(log[3](2*N/3));
if N < (2/3)*3^k then return false fi;
for a from 1 to N-1 do
L[a]:= {3*a, 3*a+1}
od:
for a from N to 2*N-1 do
L[a]:= subs(0=3*N, {3*(a-N), 3*(a-N)+1});
od:
for a from 2*N to 3*N do
L[a]:= {};
od:
L[3*N+1]:= remove(t -> has(convert(t, base, 3), 2), {$1..3*N-1}):
G:= Digraph(3*N+1, [seq(L[a], a=1..3*N+1)]);
try
ShortestPath(G, 3*N+1, 3*N);
catch "no path from": return false;
end try;
true
end proc:
select(F, [$1..1000]); # Robert Israel, Dec 03 2015
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Jeffrey Shallit, Dec 02 2015
STATUS
approved