A007302 -id:A007302 - cp's OEIS frontend

A280737 a(n) = A007302(n) - 1.

0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 2, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 2, 2, 1, 2, 2, 3

Offset: 1

N. J. A. Sloane, Jan 11 2017

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Alma D'Aniello, Aldo de Luca, and Alessandro De Luca, On Christoffel and standard words and their derivatives, arXiv:1602.03231 [cs.DM], 2016 (mentions this sequence).

Cf. A007302.

a(n)=hammingweight(bitxor(n,3*n))-1; \\ Joerg Arndt, Feb 25 2023

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Original entry on oeis.org

1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763, 699051, 2796203, 11184811, 44739243, 178956971, 715827883, 2863311531, 11453246123, 45812984491, 183251937963, 733007751851, 2932031007403, 11728124029611, 46912496118443, 187649984473771, 750599937895083

Offset: 0

Simon Plouffe

Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)-w(k), v(k+1)=u(k)-v(k)+w(k), w(k+1)=-u(k)+v(k)+w(k); let M(k)=Max(u(k),v(k),w(k)); then a(n)=M(2n)=M(2n-1). - Benoit Cloitre, Mar 25 2002
Also the number of words of length 2n generated by the two letters s and t that reduce to the identity 1 by using the relations ssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the dihedral group D6=C2xD3. - Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002
Binomial transform of A025192. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_6. Example: a(1)=3 because in the cycle ABCDEF we have three walks of length 3 between A and B: ABAB, ABCB and AFAB. - Emeric Deutsch, Apr 01 2004
Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - Artur Jasinski, Feb 09 2007
Prime numbers of the form 1+Sum[2^(2n-1)] are in A000979. Numbers x such that 1+Sum[2^(2n-1)] is prime for n=1,2,...,x is A127936. - Artur Jasinski, Feb 09 2007
Related to A024493(6n+1), A131708(6n+3), A024495(6n+5). - Paul Curtz, Mar 27 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)*charpoly(A,2). - Milan Janjic, Feb 21 2010
Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Feb 28 2011
Numbers whose binary representation is "10" repeated (n-1) times with "11" appended on the end, n >= 1. For example 171 = 10101011 (2). - Omar E. Pol, Nov 22 2012
a(n) is the smallest number for which A072219(a(n)) = 2*n+1. - Ramasamy Chandramouli, Dec 22 2012
An Engel expansion of 2 to the base b := 4/3 as defined in A181565, with the associated series expansion 2 = b + b^2/3 + b^3/(3*11) + b^4/(3*11*43) + .... Cf. A007051. - Peter Bala, Oct 29 2013
The positive integer solution (x,y) of 3*x - 2^n*y = 1, n>=0, with smallest x is (a(n/2), 2) if n is even and (a((n-1)/2), 1) if n is odd. - Wolfdieter Lang, Feb 15 2014
The smallest positive number that requires at least n additions and subtractions of powers of 2 to be formed. See Puzzling StackExchange link. - Alexander Cooke Jul 16 2023

H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..170
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Cecilia Bebeacua, Toufik Mansour, Alexander Postnikov, and Simone Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Greg Bell, Austin Lawson, Neil Pritchard, and Dan Yasaki, On locally infinite Cayley graphs of the integers, arXiv preprint arXiv:1711.00809 [math.GT], 2017. See lambda_2.
Phillip G. Bradford, Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability, arXiv:1802.05239 [cs.DS], 2018.
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D, arXiv:1507.04803 [math.CO], 2015.
Ernesto Estrada and José A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013.
Ernesto Estrada and José A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 35.
Sungpyo Hong and Jin Ho Kwak, Regular fourfold coverings with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 893
Dmitry Kamenetsky, A magic grasshopper, Puzzling StackExchange, 2023.
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv preprint arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
Quynh Nguyen, Jean Pedersen, and Hien T. Vu, New Integer Sequences Arising From 3-Period Folding Numbers, Vol. 19 (2016), Article 16.3.1.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. also A006054, A006356, A005578, A075680.
Partial sums of A081294.
Cf. A002450, A004171, A007051, A083065, A083066, A083884.
Cf. A000978, A000979, A124400, A124401, A127936, A127955, A127956, A127957, A127958.
Cf. location of records in A007302.

List([0..25], n-> (2^(2*n+1) + 1)/3); # G. C. Greubel, Dec 25 2019

a007583 = (`div` 3) . (+ 1) . a004171
-- Reinhard Zumkeller, Jan 09 2013

[(2^(2*n+1) + 1)/3: n in [0..30] ]; // Vincenzo Librandi, Apr 28 2011

a[0]:=1:for n from 1 to 50 do a[n]:=4*a[n-1]-1 od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 22 2008, with correction by K. Spage, Aug 20 2014
A007583 := proc(n)
    (2^(2*n+1)+1)/3 ;
end proc: # R. J. Mathar, Feb 19 2015

(* From Michael De Vlieger, Aug 22 2016 *)
Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
NestList[4# -1 &, 1, 23]
Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)

a(n)=sum(k=-n\3,n\3,binomial(2*n+1,n+1+3*k))

a=1; for(n=1,23, print1(a,", "); a=bitor(a,3*a)) \\ K. Spage, Aug 20 2014

Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ Altug Alkan, Dec 08 2015

apply( {A007583(n)=2<<(2*n)\/3}, [0..25]) \\ M. F. Hasler, Nov 30 2021

[(2^(2*n+1) + 1)/3 for n in (0..25)] # G. C. Greubel, Dec 25 2019

a(n) = 2*A002450(n) + 1.
From Wolfdieter Lang, Apr 24 2001: (Start)
a(n) = Sum_{m = 0..n} A060920(n, m) = A002450(n+1) - 2*A002450(n).
G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
a(n) = 4*a(n-1) - 1, n > 0.
From Paul Barry, Mar 17 2003: (Start)
a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
a(n) = A001045(2n+1). (End)
a(n) = A020988(n-1) + 1 = A039301(n+1) - 1 = A083584(n-1) + 2. - Ralf Stephan, Jun 14 2003
a(0) = 1; a(n+1) = a(n) * 4 - 1. - Regis Decamps (decamps(AT)users.sf.net), Feb 04 2004 (correction to lead index by K. Spage, Aug 20 2014)
a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - Benoit Cloitre, Mar 25 2004
a(n) = 5*a(n-1) - 4*a(n-2). - Emeric Deutsch, Apr 01 2004
a(n) = 4^n - A001045(2*n). - Paul Barry, Apr 17 2004
a(n) = 2*(A001045(n))^2 + (A001045(n+1))^2. - Paul Barry, Jul 15 2004
a(n) = left and right terms in M^n * [1 1 1] where M = the 3X3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 1 1] = [a(n) A002450(n+1) a(n)] E.g. a(3) = 43 since M^n * [1 1 1] = [43 85 43] = [a(3) A002450(4) a(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = A072197(n) - A020988(n). - Creighton Dement, Dec 31 2004
a(n) = A139250(2^n). - Omar E. Pol, Feb 28 2011
a(n) = A193652(2*n+1). - Reinhard Zumkeller, Aug 08 2011
a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - Mircea Merca, Jan 28 2012
a(n) = 2^(2*(n+1)) - A072197(n). - Vladimir Pletser, Apr 12 2014
a(n) == 2*n + 1 (mod 3). Indeed, from Regis Decamps' formula (Feb 04 2004) we have a(i+1) - a(i) == -1 (mod 3), i= 0, 1, ..., n - 1. Summing, we have a(n) - 1 == -n (mod 3), and the formula follows. - Vladimir Shevelev, May 20 2015
For n > 0 a(n) = A133494(0) + 2 * (A133494(n) + Sum_{x = 1..n - 1}Sum_{k = 0..x - 1}(binomial(x - 1, k)*(A133494(k+1) + A133494(n-x+k)))). - J. Conrad, Dec 06 2015
a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - Bob Selcoe, Aug 21 2016
E.g.f.: (1 + 2*exp(3*x))*exp(x)/3. - Ilya Gutkovskiy, Aug 21 2016
A075680(a(n)) = 1, for n > 0. - Ralf Stephan, Jun 17 2025

A278243 Filter-sequence for Stern polynomials: Least number with the same prime signature as A260443(n).

Original entry on oeis.org

1, 2, 2, 6, 2, 12, 6, 30, 2, 60, 12, 120, 6, 180, 30, 210, 2, 420, 60, 1080, 12, 2160, 120, 2520, 6, 2520, 180, 7560, 30, 6300, 210, 2310, 2, 4620, 420, 37800, 60, 90720, 1080, 75600, 12, 226800, 2160, 544320, 120, 453600, 2520, 138600, 6, 138600, 2520, 756000, 180, 2268000, 7560, 831600, 30, 415800, 6300, 2079000, 210, 485100, 2310, 30030, 2, 60060, 4620

Offset: 0

Antti Karttunen, Nov 16 2016

nonn

This sequence can be used for filtering certain Stern polynomial (see A125184, A260443) related sequences, because it matches only with any such sequence b that can be computed as b(n) = f(A260443(n)), where f(n) is any function that depends only on the prime signature of n (some of these are listed under the index entry for "sequences computed from exponents in ...").
Matching in this context means that the sequence a matches with the sequence b iff for all i, j: a(i) = a(j) => b(i) = b(j). In other words, iff the sequence b partitions the natural numbers to the same or coarser equivalence classes (as/than the sequence a) by the distinct values it obtains.
Some of these are listed on the last line ("Sequences that partition N into ...") of Crossrefs section.

Cf. A046523, A260443.
Cf. also A278222, A278226, A278234, A278235, A278236, A278261.
Sequences that partition or seem to partition N into same or coarser equivalence classes: A002487, A126606, A277314, A277315, A277325, A277326, A277700, A277705.
The following are less certain: A007302 (not proved, but the first 10000 terms match), A072453, A110955 (uncertain, but related to A007302), A218799, A218800.
Note that the base-2 related sequences A069010 and A277561 (= 2^A069010(n)) do not match, although at first it seems so, up to for at least 139 initial terms. Also A028928 belongs to a different family.

a[n_] := a[n] = Which[n < 2, n + 1, EvenQ@ n, Times @@ Map[#1^#2 & @@ # &, FactorInteger[#] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[# == 1] &@ a[n/2], True, a[#] a[# + 1] &[(n - 1)/2]]; Table[Times @@ MapIndexed[Prime[First@ #2]^#1 &, Sort[FactorInteger[#][[All, -1]], Greater]] - Boole[# == 1] &@ a@ n, {n, 0, 66}] (* Michael De Vlieger, May 12 2017 *)

(define (A278243 n) (A046523 (A260443 n)))

a(n) = A046523(A260443(n)).

A136412 a(n) = (5*4^n + 1)/3.

Original entry on oeis.org

2, 7, 27, 107, 427, 1707, 6827, 27307, 109227, 436907, 1747627, 6990507, 27962027, 111848107, 447392427, 1789569707, 7158278827, 28633115307, 114532461227, 458129844907, 1832519379627, 7330077518507, 29320310074027

Offset: 0

Paul Curtz, Mar 31 2008

An Engel expansion of 4/5 to the base b := 4/3 as defined in A181565, with the associated series expansion 4/5 = b/2 + b^2/(2*7) + b^3/(2*7*27) + b^4/(2*7*27*107) + .... Cf. A199115 and A140660. - Peter Bala, Oct 29 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Sequences of the form (m*4^n + 1)/3: A007583 (m=2), this sequence (m=5), A199210 (m=11), A199210 (m=11), A206373 (m=14).

Cf. A007302, A140660, A181565, A199115.

a136412 = (`div` 3) . (+ 1) . (* 5) . (4 ^)
-- Reinhard Zumkeller, Jun 17 2012

[(5*4^n+1)/3: n in [0..30]]; // Vincenzo Librandi, Nov 04 2011

LinearRecurrence[{5,-4}, {2,7}, 31] (* G. C. Greubel, Jan 19 2023 *)

a(n)=(5*4^n+1)/3 \\ Charles R Greathouse IV, Oct 07 2015

[(5*4^n+1)/3 for n in range(31)] # G. C. Greubel, Jan 19 2023

a(n) = 4*a(n-1) - 1.
a(n) = A199115(n)/3.
O.g.f.: (2-3*x)/((1-x)*(1-4*x)). - R. J. Mathar, Apr 04 2008
a(n) = 5*a(n-1) - 4*a(n-2). - Vincenzo Librandi, Nov 04 2011
E.g.f.: (1/3)*(5*exp(4*x) + exp(x)). - G. C. Greubel, Jan 19 2023

Formula in definition and more terms from R. J. Mathar, Apr 04 2008

A213629 In binary representation: T(n,k) = number of (possibly overlapping) occurrences of k in n, triangle read by rows, 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 1, 1, 0, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 0, 1, 3, 0, 2, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 2, 2, 0, 0, 1, 0, 0, 0, 0, 1, 3, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 3, 1, 1, 0, 1, 1, 0, 0

Offset: 1

Reinhard Zumkeller, Jun 17 2012

The definition is based on the definition of pattern functions in the paper of Allouche and Shallit;
sum of n-th row = A029931(n);
T(n,1) = A000120(n);
T(n,2) = A033264(n) for n > 1;
T(n,3) = A014081(n) for n > 2;
T(n,4) = A056978(n) for n > 3;
T(n,5) = A056979(n) for n > 4;
T(n,6) = A056980(n) for n > 5;
T(n,7) = A014082(n) for n > 6;
T(n,k) = 0 for k with floor(n/2) < k < n;
T(n,n) = 1;
A122953(n) = Sum_{k=1..n} A057427(T(n,k));
A005811(n) = T(n,1) + T(n,2) - T(n,3);
A007302(n) = A000120(n) - sum (A213629(n,A136412(k))).

			The triangle begins:
.   1:                        1
.   2:                      1   1
.   3:                    2   0   1
.   4:                  1   1   0   1
.   5:                2   1   0   0   1
.   6:              2   1   1   0   0   1
.   7:            3   0   2   0   0   0   1
.   8:          1   1   0   1   0   0   0   1
.   9:        2   1   0   1   0   0   0   0   1
.  10:      2   2   0   0   1   0   0   0   0   1
.  11:    3   1   1   0   1   0   0   0   0   0   1
.  12:  2   1   1   1   0   1   0   0   0   0   0   1.

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
J.-P. Allouche, J. Shallit, The Ring of k-regular Sequences II, Example 4, p. 12
Index entries for sequences related to binary expansion of n

Cf. A030308, A007088.

import Data.List (inits, tails, isPrefixOf)
a213629 n k = a213629_tabl !! (n-1) !! (k-1)
a213629_row n = a213629_tabl !! (n-1)
a213629_tabl = map f $ tail $ inits $ tail $ map reverse a030308_tabf where
   f xss = map (\xs ->
           sum $ map (fromEnum . (xs `isPrefixOf`)) $ tails $ last xss) xss

t[n_, k_] := (idn = IntegerDigits[n, 2]; idk = IntegerDigits[k, 2]; ln = Length[idn]; lk = Length[idk]; For[cnt = 0; i = 1, i <= ln - lk + 1, i++, If[idn[[i ;; i + lk - 1]] == idk, cnt++]]; cnt); Table[t[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 22 2012 *)

A184615 Positive parts of the nonadjacent forms for n.

Original entry on oeis.org

0, 1, 2, 4, 4, 5, 8, 8, 8, 9, 10, 16, 16, 17, 16, 16, 16, 17, 18, 20, 20, 21, 32, 32, 32, 33, 34, 32, 32, 33, 32, 32, 32, 33, 34, 36, 36, 37, 40, 40, 40, 41, 42, 64, 64, 65, 64, 64, 64, 65, 66, 68, 68, 69, 64, 64, 64, 65, 66, 64, 64, 65, 64, 64, 64, 65, 66, 68, 68, 69, 72, 72, 72, 73, 74, 80, 80, 81, 80, 80, 80, 81, 82, 84, 84, 85, 128

Offset: 0

Joerg Arndt, Jan 18 2011

nonn

This sequence together with A184616 (negated negative parts) gives the (signed binary) nonadjacent form (NAF) of n, see fxtbook link.
No two adjacent bits in the binary representations of a(n) are 1.
No two adjacent bits in the binary representations of a(n)+A184616(n) are 1.

			The first few nonadjacent forms (NAF) are
(dots are used for zeros for better readability):
     n     binary(n)  NAF(n)
   0:    .......    .......      0 =
   1:    ......1    ......P      1 =  +1
   2:    .....1.    .....P.      2 =  +2
   3:    .....11    ....P.M      3 =  +4 -1
   4:    ....1..    ....P..      4 =  +4
   5:    ....1.1    ....P.P      5 =  +4 +1
   6:    ....11.    ...P.M.      6 =  +8 -2
   7:    ....111    ...P..M      7 =  +8 -1
   8:    ...1...    ...P...      8 =  +8
   9:    ...1..1    ...P..P      9 =  +8 +1
  10:    ...1.1.    ...P.P.     10 =  +8 +2
  11:    ...1.11    ..P.M.M     11 =  +16 -4 -1
  12:    ...11..    ..P.M..     12 =  +16 -4
  13:    ...11.1    ..P.M.P     13 =  +16 -4 +1
  14:    ...111.    ..P..M.     14 =  +16 -2
  15:    ...1111    ..P...M     15 =  +16 -1
  16:    ..1....    ..P....     16 =  +16
  17:    ..1...1    ..P...P     17 =  +16 +1
  18:    ..1..1.    ..P..P.     18 =  +16 +2
This sequence gives the words obtained by keeping the 'P' (sum of positive terms in rightmost column), keeping the 'M' gives A184616 (negative sum of negative terms in rightmost column).

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Pages 61-62 of Matters Computational (The Fxtbook).

A184616 (negated negative parts), A184617 (sums of both parts =A184615+A184616).

A007302 gives the number of nonzero bits ('M' and 'P' in example).

bin2naf[x_] := Module[{xh, x3, c, np, nm},
  xh = BitShiftRight[x, 1];
  x3 = x + xh;
  c = BitXor[xh, x3];
  np = BitAnd[x3, c];
  nm = BitAnd[xh, c];
  Return[{np, nm}]];
a[n_] := bin2naf[n][[1]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 30 2019, from PARI *)

bin2naf(x)=
{ /* Compute (nonadjacent) signed binary representation of x: */
    local(xh,x3,c,np,nm);
    xh = x >> 1;
    x3 = x + xh;
    c = bitxor(xh, x3);
    np = bitand(x3, c);  /* bits == +1 */
    nm = bitand(xh, c);  /* bits == -1 */
    return([np,nm]);  /* np-nm==x */
}
{ for(n=0,100, v = bin2naf(n); print1(v[1],", "); ); } /* show terms */
{ for(n=0,100, v = bin2naf(n); print1(v[2],", "); ); } /* terms of A184616 */
{ for(n=0,100, v = bin2naf(n); print1(v[1]+v[2],", "); ); } /* terms of A184617 */
{ for(n=0,100, v = bin2naf(n); print1(v[1]-v[2],", "); ); }  /* == n */

a(n) - A184616(n) = n

a(n) + A184616(n) = A184617(n)

A334913 a(n) is the sum of digits of n in signed binary nonadjacent form.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 0, 0, 1, 2, 2, -1, 0, 1, 0, 0, 1, 2, 2, 1, 2, 3, -1, -1, 0, 1, 1, -1, 0, 1, 0, 0, 1, 2, 2, 1, 2, 3, 1, 1, 2, 3, 3, -2, -1, 0, -1, -1, 0, 1, 1, 0, 1, 2, -1, -1, 0, 1, 1, -1, 0, 1, 0, 0, 1, 2, 2, 1, 2, 3, 1, 1, 2, 3, 3, 0, 1, 2, 1, 1, 2, 3, 3, 2

Offset: 0

Lei Zhou, May 16 2020

Joerg Arndt, Matters Computational - Ideas, Algorithms, Source Code, 2011, Springer, pp. 61-62.
Helmut Prodinger, On binary representations of integers with digits -1,0,1, Integers 0 (2000), #A08.

Cf. A000120, A001045, A007302, A184615, A184616.

BBN[a_] := Module[{n = a, b}, b = IntegerDigits[n, 2]; b = Prepend[b, 0];
  l = Length[b];
  Do[If[b[[i]] == 2, b[[i]] = 0; b[[i - 1]]++,
    If[b[[i]] == 1,
     If[b[[i + 1]] == 1, b[[i - 1]]++; b[[i]] = 0;
      b[[i + 1]] = -1]]], {i, l - 1, 2, -1}];
  If[b[[1]] == 0, b = Delete[b, 1]]; b]
Table[a = BBN[i]; sod = 0; l = Length[a];
Do[sod = sod + a[[j]], {j, 1, l}]; sod, {i, 0, 83}]

bin2naf(x)=
{ /* Compute (nonadjacent) signed binary representation of x: */
    local(xh, x3, c, np, nm);
    xh = x >> 1;
    x3 = x + xh;
    c = bitxor(xh, x3);
    np = bitand(x3, c);  /* bits == +1 */
    nm = bitand(xh, c);  /* bits == -1 */
    return([np, nm]);  /* np-nm==x */
}
a(n) = my(b=bin2naf(n)); return(hammingweight(b[1])-hammingweight(b[2]));
vector(99,n,a(n-1)) \\ Joerg Arndt, Jun 13 2020

a(n) = hammingweight(A184615(n)) - hammingweight(A184616(n)). - Joerg Arndt, Jun 13 2020

A085424 Number of ones in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)_2 number system).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1

Offset: 1

Ralf Stephan, Jun 30 2003

Wieb Bosma, Signed bits and fast exponentiation, J. Th. Nombres de Bordeaux, 13 no. 1 (2001), p. 27-41.
C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.

Cf. A005578, A085423, A007302 (nonzeros), A057526 (0's), A085425 (-1's).

ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6);
a(n)=sum(r=0, log(3*n)\log(2)-1, (ep(r, n) == 1)) ;

A085425 Number of minus ones in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)_2 number system).

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 3, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1

Offset: 1

Ralf Stephan, Jun 30 2003

C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.

Cf. A005578, A085423, A007302 (nonzeros), A057526 (0's), A085424 (1's).

ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6);
a(n)=sum(r=0, log(3*n)\log(2)-1, (ep(r, n) == 1)) ;

A110955 Number of minimal signed binary representations for an integer n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 4, 3, 5, 2, 2, 2, 2, 2, 5, 3, 4, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 4, 3, 3, 3, 5, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2

Offset: 0

Joe Sawada, Sep 26 2005

nonn

A. D. Booth, A signed binary multiplication technique, Quarterly Journal on Mechanics and Applied Mathematics, Vol. 4 (1951) 236-240.
G. Manku and J. Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669, (2005) 438-447.
J. Sawada, A Gray code for binary subtraction, 2nd Brazilian Conference on Graphs, Algorithms and Combinatorics (GRACO), Electronic Notes in Discrete Mathematics, 19 (2005) 125-131.
J. Sawada, A simple Gray code to list all minimal signed binary representations, SIAM Journal on Discrete Mathematics, Vol. 21 No. 1 (2007), 16-25.

Cf. A007302.

cp's OEIS Frontend

A280737 a(n) = A007302(n) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

A278243 Filter-sequence for Stern polynomials: Least number with the same prime signature as A260443(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A136412 a(n) = (5*4^n + 1)/3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A213629 In binary representation: T(n,k) = number of (possibly overlapping) occurrences of k in n, triangle read by rows, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A184615 Positive parts of the nonadjacent forms for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334913 a(n) is the sum of digits of n in signed binary nonadjacent form.

Views