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

1, 3, 4, 7, 9, 10, 12, 13, 19, 21, 22, 25, 27, 28, 30, 31, 34, 36, 37, 39, 40, 55, 57, 58, 61, 63, 64, 66, 67, 70, 73, 75, 76, 79, 81, 82, 84, 85, 88, 90, 91, 93, 94, 97, 100, 102, 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

Offset: 1

Author

Jeffrey Shallit, Dec 02 2015

Keywords

• nonn
• base

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

Examples

			7 is in the sequence because it can be expressed as 28/4, and in base 3 28 is 1001 and 4 is 11.
		

Links

• Jeffrey Shallit and Robert Israel, Table of n, a(n) for n = 1..1000 (n = 1..399 from Jeffrey Shallit)

Crossrefs

Cf. A005836.

Programs

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