A037096 -id:A037096 - cp's OEIS frontend

A036284 Periodic vertical binary vectors of Fibonacci numbers.

6, 24, 1440, 5728448, 92568198012160, 26494530374406845814111659520, 2095920895719545919920115988669687683503034097906010941440, 13128614603426246034591796912897206548807135027496968025827278400248602613784037111736380004928525614173642247188480

Offset: 0

Antti Karttunen, Nov 01 1998

The sequence can be also computed with a recurrence that does not explicitly refer to Fibonacci numbers. See the given Maple and C programs.

Conjecture: For n>=1, each term a(n), when considered as a GF(2)[X]-polynomial, is divisible by GF(2)[X] -polynomial (x^3 + 1) ^ A000225(n-1). If this holds, then for n>=1, a(n) = A048720bi(A136380(n),A048723bi(9,A000225(n-1))). Conjecture 2: there is also one extra (x^1 + 1) factor present, see A136384.

			When Fibonacci numbers are written in binary (see A004685), under each other as:
0000000 (0)
0000001 (1)
0000001 (1)
0000010 (2)
0000011 (3)
0000101 (5)
0001000 (8)
0001101 (13)
0010101 (21)
0100010 (34)
0110111 (55)
1011001 (89)
it can be seen that the bits in the n-th column from right repeat after a period of A007283(n): 3, 6, 12, 24, ... (See also A001175). This sequence is formed from those bits: 011, reversed is 110, is binary for 6, thus a(0) = 6. 000110, reversed is 11000, is binary for 24, thus a(1) = 24, 000001011010, reversed is 10110100000, is binary for 1440, thus a(2) = 1440.

A. Karttunen, Table of n, a(n) for n = 0..10
A. Karttunen, C program for computing this sequence

Same sequence in octal base: A036285. Bits reversed: A036286. See also A136378, A136379, A136380, A136382, A136384, A037096, A037093, A000045.

A036284:=proc(n) option remember; local a, b, c, i, j, k, l, s, x, y, z; if (0 = n) then (6) else a := 0; b := 0; s := 0; x := 0; y := 0; k := 3*(2^(n-1)); l := 3*(2^n); j := 0; for i from 0 to l do z := bit_i(A036284(n-1),(j)); c := (a + b + (`if`((x = y),x,(z+1))) mod 2); if(c <> 0) then s := s + (2^i); fi; a := b; b := c; x := y; y := z; j := j + 1; if(j = k) then j := 0; fi; od; RETURN(s); fi; end:
bit_i := (x,i) -> `mod`(floor(x/(2^i)),2);

a[n_] := Sum[Mod[Fibonacci[k]/2^n // Floor, 2]* 2^k, {k, 0, 3*2^n - 1}]; Table[a[n], {n, 0, 7}] (* Jean-François Alcover, Mar 04 2016 *)

a(n) = Sum_{k=0..A007283(n)-1} ([A000045(k)/(2^n)] mod 2) * 2^k, where [] stands for floor function, i.e. Sum (bit n of Fibonacci(k))*(2^k), k = 0 ... (3*(2^n))-1.

Entry revised Dec 29 2007

A268389 a(n) = greatest k such that polynomial (X+1)^k divides the polynomial (in polynomial ring GF(2)[X]) that is encoded in the binary expansion of n. (See the comments for details).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0, 3, 0, 4, 1, 0, 2, 0, 0, 1, 1, 0, 0, 2, 0, 1, 3, 0, 0, 1, 4, 0, 1, 0, 0, 2, 2, 0, 0, 1, 0, 3, 1, 0, 1, 0, 0, 5, 0, 1, 2, 0, 0, 2, 1, 0, 3, 0, 0, 1, 0, 2, 1, 0, 4, 0, 0, 1, 1, 0, 0, 3, 0, 1, 2, 0, 2, 0, 0, 1, 0, 6, 1, 0, 0, 1, 3, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 1, 5, 0, 0, 3, 1, 0, 2, 0, 0, 1, 0, 1, 2, 0, 1, 0, 0, 4, 3

Offset: 1

Antti Karttunen, Feb 10 2016

a(n) gives the number of iterations of map k -> A006068(k)/2 that are required (when starting from k = n) until k is an odd number.
A001317 gives the record positions and particularly, A001317(n) gives the first occurrence of n in this sequence.
When polynomials over GF(2) are encoded in the binary representation of n in a natural way where each polynomial b(n)*X^n+...+b(0)*X^0 over GF(2) is represented by the binary number b(n)*2^n+...+b(0)*2^0 in N (each coefficient b(k) is either 0 or 1), then a(n) = the number of times polynomial X+1 (encoded by 3, "11" in binary) divides the polynomial encoded by n.

			For n = 5 ("101" in binary) which encodes polynomial x^2 + 1, we see that it can be factored over GF(2) as (X+1)(X+1), and thus a(5) = 2.
For n = 8 ("1000" in binary) which encodes polynomial x^3, we see that it is not divisible in ring GF(2)[X] by polynomial X+1, thus a(8) = 0.
For n = 9 ("1001" in binary) which encodes polynomial x^3 + 1, we see that it can be factored over GF(2) as (X+1)(X^2 + X + 1), and thus a(9) = 1.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A001317, A006068, A007949, A048720, A048723, A048724, A057889, A268384, A235042, A268670.
Cf. A268669 (quotient left after (X+1)^a(n) has been divided out).
Cf. A268395 (partial sums).
Cf. A000069 (positions of zeros), A268679 (this sequence without zeros).
Cf. also A037096, A037097, A136386.

f[n_] := Which[n == 1, 0, OddQ@ #, 0, EvenQ@ #, 1 + f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Array[f, {120}] (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)

a(n) = {my(b = binary(n), p = Pol(binary(n))*Mod(1,2), k = poldegree(p)); while (type(p/(x+1)^k*Mod(1,2)) != "t_POL", k--); k;} \\ Michel Marcus, Feb 12 2016

;; This employs the given recurrence and uses memoization-macro definec:
(definec (A268389 n) (if (odd? (A006068 n)) 0 (+ 1 (A268389 (/ (A006068 n) 2)))))
(define (A268389 n) (let loop ((n n) (s 0)) (let ((k (A006068 n))) (if (odd? k) s (loop (/ k 2) (+ 1 s)))))) ;; Computed in a loop, no memoization.

If A006068(n) is odd, then a(n) = 0, otherwise a(n) = 1 + a(A006068(n)/2).
Other identities. For all n >= 0:
a(A001317(n)) = n. [The sequence works as a left inverse of A001317.]
A048720(A268669(n),A048723(3,a(n))) = A048720(A268669(n),A001317(a(n))) = n.
A048724^a(n) (A268669(n)) = n. [The a(n)-th fold application (power) of A048724 when applied to A268669(n) gives n back.]
a(n) = A007949(A235042(n)).
a(A057889(n)) = a(n).

A037095 "Sloping binary representation" of powers of 3 (A000244), slope = -1.

Original entry on oeis.org

1, 1, 3, 1, 3, 9, 11, 17, 19, 25, 123, 65, 195, 169, 171, 753, 435, 249, 2267, 4065, 8163, 841, 843, 31313, 29651, 39769, 38331, 30081, 160643, 49769, 53867, 563377, 700659, 1611961, 760731, 1207073, 5668771, 5566345, 11844619, 8699025, 10386067, 55868313

Offset: 0

Antti Karttunen, Jan 28 1999

			When powers of 3 are written in binary (see A004656), under each other as:
  000000000001 (1)
  000000000011 (3)
  000000001001 (9)
  000000011011 (27)
  000001010001 (81)
  000011110011 (243)
  001011011001 (729)
  100010001011 (2187)
and one collects their bits from the column-0 to NW-direction (from the least to the most significant end), one gets 1 (1), 01 (1), 011 (3), 0001 (1), 00011 (3), 001001 (9), etc. (See A105033 for similar transformation done on nonnegative integers, A001477).

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Cf. A105033, A000244, A037093, A037094, A037096, A037097, A339601.

A037095:= n-> add(bit_n(3^(n-i), i)*(2^i), i=0..n):
bit_n := (x, n) -> `mod`(floor(x/(2^n)), 2):
seq(A037095(n), n=0..41);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1, (p->
       expand((p-(p mod 2))*x/2)+3^n)(b(n-1)))
    end:
a:= n-> subs(x=2, b(n) mod 2):
seq(a(n), n=0..42);  # Alois P. Heinz, Dec 10 2020

A339601(n) = { my(m=1, s=0); while(n>=m, s += bitand(m,n); m <<= 1; n \= 3); (s); };
A037095(n) = A339601(3^n); \\ Antti Karttunen, Dec 09 2020

BINSLOPE(f) = n -> sum(i=0,n,bitand(2^(n-i),f(i))); \\ General transformation for these kinds of sequences.
A037095 = BINSLOPE(n -> 3^n); \\ And its application to A000244. - Antti Karttunen, Dec 09 2020

a(n) = A339601(A000244(n)). - Antti Karttunen, Dec 09 2020

Entry revised Dec 29 2007

More terms from Sean A. Irvine, Dec 08 2020

A136386 Quotient obtained when A037097(n) is considered as a GF(2)[X]-polynomial and it is divided by (x + 1) ^ A000225(n-1) (= A051179(n-2)).

Original entry on oeis.org

4, 8, 352, 3728, 7269662752, 761166466256046848, 390022035611646394530728097023856870592, 91600670557117582933643002658167825054614175029432880501373395030525438396928, 13417853484388319477475698658536993288839029124735549539652836318808118017743106800015257954250357092148394821846783842030516713870361254572407216621548672

Offset: 3

Antti Karttunen, Dec 29 2007

A. Karttunen, Table of n, a(n) for n = 3..13
A. Karttunen, C program for computing this sequence

A136387 shows the same sequence in binary base. Cf. A037096, A037097, A136380, A136382, A136384.

A037097 Periodic vertical binary vectors of powers of 3, starting from bit-column 2 (halved).

Original entry on oeis.org

0, 12, 120, 57120, 93321840, 10431955353116229600, 8557304989566294213168677685339060480, 102743047168201563425402150421568484707810385382513037790885688657488312400960

Offset: 2

Antti Karttunen, Jan 29 1999

Conjecture: For n>=3, each term a(n), when considered as a GF(2)[X]-polynomial, is divisible by GF(2)[X] -polynomial (x + 1) ^ A000225(n-1) (= A051179(n-2)). If this holds, then for n>=3, a(n) = A048720bi(A136386(n),A048723bi(3,A000225(n-1))) = A048720bi(A136386(n),A051179(n-2)).

			When powers of 3 are written in binary (see A004656), under each other as:
000000000001 (1)
000000000011 (3)
000000001001 (9)
000000011011 (27)
000001010001 (81)
000011110011 (243)
001011011001 (729)
100010001011 (2187)
it can be seen that, starting from the column 2 from the right, the bits in the n-th column can be arranged in periods of 2^(n-1): 4, 8, ... This sequence is formed from those bits: 0011, reversed is 11100, which is binary for 12, thus a(3) = 12, 00011110, reversed is 011110000, which is binary for 120, thus a(4) = 120.

S. Wolfram, A New Kind of Science, Wolfram Media Inc., (2002), p. 119.

A. Karttunen, Table of n, a(n) for n = 2..12
A. Karttunen, C program for computing this sequence
S. Wolfram, A New Kind of Science, Wolfram Media Inc., (2002), p. 119.

a(n) = floor(A037096(n)/(2^(2^(n-1)))). See also A036284, A136386.

a(n) := sum( 'bit_n(3^i, n)*(2^i)', 'i'=0..(2^(n-1))-1);
bit_n := (x, n) -> `mod`(floor(x/(2^n)), 2);

a(n) = Sum_{k=0..A000225(n-1)} ([A000244(k)/(2^n)] mod 2) * 2^k, where [] stands for floor function.

Entry revised Dec 29 2007

A265210 Irregular triangle read by rows in which row n lists the base 3 digits of 2^n in reverse order, n >= 0.

Original entry on oeis.org

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

Offset: 0

L. Edson Jeffery, Dec 04 2015

The length of row n is A020915(n) = 1 + A136409(n).

Conjecture 1: The sequence in column k is periodic, with period p(k) = 2*3^(k-1) = A008776(k-1), k >= 1, and in which the numbers 0,1,2 appear with equal frequency, for each k>1.

			n
0:    1
1:    2
2:    1  1
3:    2  2
4:    1  2  1
5:    2  1  0  1
6:    1  0  1  2
7:    2  0  2  1  1
8:    1  1  1  0  0  1
9:    2  2  2  0  0  2
10:   1  2  2  1  0  1  1
11:   2  1  2  0  1  2  2
12:   1  0  2  1  2  1  2  1
13:   2  0  1  0  2  0  2  0  1
14:   1  1  2  0  1  1  1  1  2
15:   2  2  1  1  2  2  2  2  1  1

Cf. A000079 (powers of 2), A004642 (powers of 2 written in base 3), A008776 (2*3^n).
Cf. A265209 (base 3 digits of 2^n).
Cf. A264980 (row n read as ternary number).
Cf. A037096 (numbers constructed from the inverse case, base 2 digits of 3^n).

(* Replace Flatten with Grid to display the triangle: *)
Flatten[Table[Reverse[IntegerDigits[2^n, 3]], {n, 0, 15}]]

A265210_row(n)=Vecrev(digits(2^n,3)) \\ M. F. Hasler, Dec 05 2015

cp's OEIS Frontend

A036284 Periodic vertical binary vectors of Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A268389 a(n) = greatest k such that polynomial (X+1)^k divides the polynomial (in polynomial ring GF(2)[X]) that is encoded in the binary expansion of n. (See the comments for details).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A037095 "Sloping binary representation" of powers of 3 (A000244), slope = -1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

Extensions

A136386 Quotient obtained when A037097(n) is considered as a GF(2)[X]-polynomial and it is divided by (x + 1) ^ A000225(n-1) (= A051179(n-2)).

Views

Author

Keywords

Links

Crossrefs

A037097 Periodic vertical binary vectors of powers of 3, starting from bit-column 2 (halved).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A265210 Irregular triangle read by rows in which row n lists the base 3 digits of 2^n in reverse order, n >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI