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,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

Cf. A005836.

Sequence in context: A026225 A026140 A233010 * A344416 A330178 A059010

Adjacent sequences: A263485 A263486 A263487 * A263489 A263490 A263491

Keyword

nonn,base

Author

Jeffrey Shallit, Dec 02 2015

Status

approved