This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
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.
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.
For n = 5 ("101" in binary) which encodes polynomial x^2 + 1, we observe that it can be factored in ring GF(2)[X] as (X+1)(X+1), and thus a(5) = 1, because after dividing both instances of (X+1) off, we are left with the quotient polynomial 1 which is encoded by 1.
For n = 8 ("1000" in binary) which encodes polynomial x^3, we observe that it is not divisible in ring GF(2)[X] by polynomial X+1, thus a(8) = 8.
For n = 9 ("1001" in binary) which encodes polynomial x^3 + 1, we observe that it can be factored over GF(2) as (X+1)(X^2 + X + 1), and thus a(9) = 7, because the quotient polynomial X^2 + X + 1 is encoded by 7 ("111" in binary).
f[n_] := If[OddQ@ #, n, f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Array[f, {85}] (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)
a(n) = {p = Pol(binary(n))*Mod(1,2); q = (x+1)*Mod(1,2); while (type(r = p/q) == "t_POL", p = r); np = Polrev(vector(poldegree(p)+1, k, k--; lift(polcoeff(p, k)))); subst(np, x, 2);} \\ Michel Marcus, Feb 12 2016
;; This employs the given recurrence and uses memoization-macro definec: (definec (A268669 n) (if (odd? (A006068 n)) n (A268669 (/ (A006068 n) 2)))) (define (A268669 n) (let loop ((n n)) (let ((k (A006068 n))) (if (odd? k) n (loop (/ k 2)))))) ;; Computed in a loop, no memoization.
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 the bits in the n-th column from the right can be arranged in periods of 2^n: 1, 2, 4, 8, ... This sequence is formed from those bits: 1, is binary for 1, thus a(0) = 1. 01, reversed is 10, which is binary for 2, thus a(1) = 2, 0000 is binary for 0, thus a(2)=0, 000110011, reversed is 11001100 = A007088(204), thus a(3) = 204.
a(n) := sum( 'bit_n(3^i, n)*(2^i)', 'i'=0..(2^(n))-1); bit_n := (x, n) -> `mod`(floor(x/(2^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.
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);
Comments