login
Balanced ternary enumeration (based on balanced ternary representation) of integers; write n in ternary and then replace 2's with (-1)'s.
48

%I #87 Mar 10 2021 07:23:14

%S 0,1,-1,3,4,2,-3,-2,-4,9,10,8,12,13,11,6,7,5,-9,-8,-10,-6,-5,-7,-12,

%T -11,-13,27,28,26,30,31,29,24,25,23,36,37,35,39,40,38,33,34,32,18,19,

%U 17,21,22,20,15,16,14,-27,-26,-28,-24,-23,-25,-30,-29,-31,-18,-17,-19,-15,-14,-16,-21,-20,-22,-36

%N Balanced ternary enumeration (based on balanced ternary representation) of integers; write n in ternary and then replace 2's with (-1)'s.

%C As the graph demonstrates, there are large discontinuities in the sequence between terms 3^i-1 and 3^i, and between terms 2*3^i-1 and 2*3^i. - _N. J. A. Sloane_, Jul 03 2016

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, pp. 173-175; 2nd. ed. pp. 190-193.

%H Gheorghe Coserea, <a href="/A117966/b117966.txt">Table of n, a(n) for n = 0..59048</a> (first 729 terms from A. Karttunen)

%H Ken Levasseur, <a href="http://discretemath.org/ternary_number_system.html">The Balanced Ternary Number System</a>

%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:Balanced_ternary_A117966.svg">First 27 numbers with their ternary representation</a>

%H N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=o8c4uYnnNnc">Amazing Graphs II (including Star Wars)</a>, Numberphile video (2019)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Balanced_ternary">Balanced ternary</a>

%F a(0) = 0, a(3n) = 3a(n), a(3n+1) = 3a(n)+1, a(3n+2) = 3a(n)-1.

%F G.f. satisfies A(x) = 3*A(x^3)*(1+x+x^2) + x/(1+x+x^2). - corrected by _Robert Israel_, Nov 17 2015

%F A004488(n) = a(n)^{-1}(-a(n)). I.e., if a(n) <= 0, A004488(n) = A117967(-a(n)) and if a(n) > 0, A004488(n) = A117968(a(n)).

%F a(n) = n - 3 * A005836(A289814(n) + 1). - _Andrey Zabolotskiy_, Nov 11 2019

%e 7 in base 3 is 21; changing the 2 to a (-1) gives (-1)*3+1 = -2, so a(7) = -2. I.e., the number of -2 according to the balanced ternary enumeration is 7, which can be obtained by replacing every -1 by 2 in the balanced ternary representation (or expansion) of -2, which is -1,1.

%p f:= proc(n) local L,i;

%p L:= subs(2=-1,convert(n,base,3));

%p add(L[i]*3^(i-1),i=1..nops(L))

%p end proc:

%p map(f, [$0..100]);

%p # alternate:

%p N:= 100: # to get a(0) to a(N)

%p g:= 0:

%p for n from 1 to ceil(log[3](N+1)) do

%p g:= convert(series(3*subs(x=x^3,g)*(1+x+x^2)+x/(1+x+x^2),x,3^n+1),polynom);

%p od:

%p seq(coeff(g,x,j),j=0..N); # _Robert Israel_, Nov 17 2015

%p # third Maple program:

%p a:= proc(n) option remember; `if`(n=0, 0,

%p 3*a(iquo(n, 3, 'r'))+`if`(r=2, -1, r))

%p end:

%p seq(a(n), n=0..3^4-1); # _Alois P. Heinz_, Aug 14 2019

%t Map[FromDigits[#, 3] &, IntegerDigits[#, 3] /. 2 -> -1 & /@ Range@ 80] (* _Michael De Vlieger_, Nov 17 2015 *)

%o (MIT/GNU Scheme:) (define (A117966 n) (let loop ((z 0) (i 0) (n n)) (if (zero? n) z (loop (+ z (* (expt 3 i) (if (= 2 (modulo n 3)) -1 (modulo n 3)))) (1+ i) (floor->exact (/ n 3)))))) -- _Antti Karttunen_, May 19 2008

%o (PARI) a(n) = subst(Pol(apply(x->if(x == 2, -1, x), digits(n,3)), 'x), 'x, 3)

%o vector(73, i, a(i-1)) \\ _Gheorghe Coserea_, Nov 17 2015

%o (Python)

%o def a(n):

%o if n==0: return 0

%o if n%3==0: return 3*a(n//3)

%o elif n%3==1: return 3*a((n - 1)//3) + 1

%o else: return 3*a((n - 2)//3) - 1

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 06 2017

%Y Cf. A117967, A117968, A001057, A004488, A134028, A274107, A059095, A005836, A289814, A244042.

%Y Column k=1 of A319047.

%K base,sign,look

%O 0,4

%A _Franklin T. Adams-Watters_, Apr 05 2006

%E Name corrected by _Andrey Zabolotskiy_, Nov 10 2019