A004198 -id:A004198 - cp's OEIS frontend

A075173 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A075300.

0, 1, 2, 5, 8, 3, 128, 21, 34, 9, 32768, 7, 2147483648, 129, 10, 85, 9223372036854775808, 35, 170141183460469231731687303715884105728, 13, 130, 32769

Offset: 1

Antti Karttunen, Sep 13 2002

nonn

As in A059884, here also we store the exponent e_i of p_i (p1=2, p2=3, p3=5, ...) in the factorization of n to the bit positions given by the column i-1 of A075300 (the exponent of 2 is thus stored to bit positions 0, 2, 4, ..., exponent of 3 to 1, 5, 9, 13, ..., exponent of 5 to 3, 11, 19, 27, 35, ...), but using unary instead of binary system, i.e. we actually store 2^(e_i) - 1 in binary.

This injective mapping from N to N offers an example of the proof given in Cameron's book that any distributive lattice can be represented as a sublattice of the power-set lattice P(X) of some set X. This allows us to implement GCD (A003989) with bitwise AND (A004198) and LCM (A003990) with bitwise OR (A003986). Also, to test whether x divides y, it is enough to check that ((a(x) OR a(y)) XOR a(y)) = A003987(A003986(a(x),a(y)),a(y)) is zero.

			a(24) = 23 because 24 = 2^3 * 3^1 so we add the binary words 10101 and 10 to get 10111 in binary = 23 in decimal and a(25) = 2056 because 25 = 5^2 so we form a binary word 100000001000 = 2056 in decimal.

P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1998, page 191. (12.3. Distributive lattices)

Variant: A075175. Inverse: A075174. Cf. A059884.

A003989(x, y) = A075174(A004198(a(x), a(y))), A003990(x, y) = A075174(A003986(a(x), a(y))).

A292592 a(n) = A292590(A245612(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 2, 2, 0, 1, 0, 0, 4, 5, 4, 5, 0, 0, 2, 2, 0, 1, 0, 0, 8, 8, 10, 11, 8, 8, 10, 10, 0, 1, 0, 0, 4, 5, 4, 5, 0, 0, 2, 2, 0, 1, 0, 0, 16, 17, 16, 17, 20, 20, 22, 23, 16, 17, 16, 16, 20, 21, 20, 21, 0, 0, 2, 2, 0, 1, 0, 0, 8, 8, 10, 11, 8, 8, 10, 10, 0, 1, 0, 0, 4, 5, 4, 5, 0, 0, 2, 2, 0, 1, 0, 0, 32, 32, 34, 35, 32, 32, 34, 34, 40, 41, 40, 41

Offset: 0

Antti Karttunen, Sep 20 2017

Because A292590(n) = a(A245611(n)), the sequence works as a "masking function" where the 1-bits in a(n) (always a subset of the 1-bits in binary expansion of n) indicate which numbers are multiples of 3 in binary tree A245612 on that trajectory which leads from the root of the tree to the node containing A245612(n). See the examples.

			A245612(18) = 188, that is, at "node address" 18 in binary tree A245612 sits number 188. 18 in binary is "10010", which when read from left to right (after the most significant bit which is always 1) gives the directions to follow in the tree when starting from the root, to land in node containing number 188. Here, after 1 and 2, turn left from 2, turn left from 5, turn right from 14 and then turn left from 63 and then indeed one lands in 188. These turns correspond with the four lowermost bits of the code, "0010". When one selects multiples of 3 from this path 1 -> 2 -> 5 -> 14 -> 63 -> 188, the only one is 63, which corresponds with the second rightmost bit (which also is the only 1-bit) in the code, which can be masked with 2 (binary "10"), thus a(18) = 2.
A245612(15) = 6, that is, at "node address" 15 in binary tree A245612 sits number 6. 15 in binary is "1111", which tells that 6 can be located in tree A245612 by going (after the initial root 1 and 2) three steps towards right from 2: 1 -> 2 -> 3 -> 4 -> 6. Of these numbers, only 3 and 6 are multiples of 3, thus the mask to obtain the corresponding bits from "1111" is "00101" (5 in binary), thus a(15) = 5.
A245612(31) = 7, that is, at "node address" 31 in binary tree A245612 sits number 7. 31 in binary is "11111", which tells that 7 can be located in tree A245612 by going (after the initial root 1 and 2) four steps towards right from 2: 1 -> 2 -> 3 -> 4 -> 6 -> 7. Of these numbers, only 3 and 6 are multiples of 3, thus the mask to obtain the corresponding bits from "11111" is "001010" (ten in binary), thus a(31) = 10.

Cf. A004198, A292590, A292593.
Cf. also A292377.
Differs from related A292274 for the first time at n=31, where a(31) = 10, while A292274(31) = 11. Compare also the scatter plots.

f[n_] := f[n] = Which[n == 1, 0, Mod[n, 3] == 2, Ceiling[n/3], True, (Times @@ Power[If[# == 1, 1, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger[2 n - 1] + 1)/2]; g[n_] := g[n] = If[n == 1, 0, 2 g[f@ n] + Boole[Divisible[n, 3]]]; h[n_] := (Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@If[n == 0, 1, Prime[#] Product[ Prime[m]^(Map[ Ceiling[(Length@ # - 1)/2] &, DeleteCases[ Split@ Join[ Riffle[ IntegerDigits[n, 2], 0], {0}], {k__} /;k == 1]][[-m]]), {m, #}] &[DigitCount[n, 2, 1]]]; Array[g@ h@ # &, 108, 0] (* Michael De Vlieger, Sep 22 2017 *)

a(n) + A292593(n) = n, a(n) AND A292593(n) = 0.

a(n) AND n = a(n), where AND is bitwise-AND (A004198).

A292944 a(n) = A292272(A004754(n)) - 2*A053644(n).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 2, 2, 0, 1, 2, 2, 4, 5, 4, 4, 0, 1, 2, 2, 4, 5, 4, 4, 8, 9, 10, 10, 8, 9, 8, 8, 0, 1, 2, 2, 4, 5, 4, 4, 8, 9, 10, 10, 8, 9, 8, 8, 16, 17, 18, 18, 20, 21, 20, 20, 16, 17, 18, 18, 16, 17, 16, 16, 0, 1, 2, 2, 4, 5, 4, 4, 8, 9, 10, 10, 8, 9, 8, 8, 16, 17, 18, 18, 20, 21, 20, 20, 16, 17, 18, 18, 16, 17, 16, 16, 32, 33, 34, 34, 36, 37, 36, 36

Offset: 0

Antti Karttunen, Sep 28 2017

In binary expansion (A007088) of n, clear the most significant bit and all those 1-bits that have another 1-bit at their left side, except for the second most significant 1-bit, even in cases where the binary expansion begins as "11...".

Because A292943(n) = a(A243071(n)), the sequence works as a "masking function" where the 1-bits in a(n) (always a subset of the 1-bits in binary expansion of n) indicate which numbers are of the form 6k+3 (odd multiples of three) in binary tree A163511 (or its mirror image tree A005940) on that trajectory which leads from the root of the tree to the node containing A163511(n).

			For n = 23, 10111 in binary, when we clear (change to zero) the most significant bit (always 1) and also all 1-bits that have 1's at their left side, we are left with 100, which in binary stands for 4, thus a(23) = 4.
For n = 27, 11011 in binary, when we clear the most significant bit, and also all 1-bits that have 1's at their left side except the second most significant, we are left with 1010, which in binary stands for ten, thus a(27) = 10.

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences related to binary expansion of n

Cf. A004754, A005940, A048735, A163511, A292272, A292943.

Cf. also A292247, A292248, A292254, A292256, A292264, A292271, A292274, A292592, A292593, A292942, A292946.

(define (A292944 n) (let ((x (+ n (A053644 n)))) (- (A292272 x) (A053644 x))))
(define (A292944 n) (- (A292272 (A004754 n)) (* 2 (A053644 n))))
(define (A292944 n) (A292943 (A163511 n)))

a(n) = A292272(A004754(n)) - 2*A053644(n).
a(n) = A292943(A163511(n)).
Other identities. For all n >= 0:
a(n) + A292264(n) = A292942(n) + a(n) + A292946(n) = a(n) + A292254(n) + A292256(n) = n.
a(n) = a(n) AND n; a(n) AND A292264(n) = 0, where AND is bitwise-and (A004198).

A050602 Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 22 1999

Array is symmetric and is read by antidiagonals: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0),  etc. - Antti Karttunen, Sep 04 2023
Comment from N. J. A. Sloane, Jun 21 2011: Apparently the same as the following sequence. Infinite square array read by antidiagonals, where T(m,n) = length of longest carry propagation when u and v are added in binary, for u >= 0, v >= 0.
See A192054 for definition of carry propagation. For example, T(3,5) = 3, since adding 011 + 101 in binary, the initial 1 propagates three places.

			The top left corner of the square array:
     |  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
-----+--------------------------------------------------------
   0 |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,
   1 |  0, 1, 0, 2, 0, 1, 0, 3, 0, 1,  0,  2,  0,  1,  0,  4,
   2 |  0, 0, 1, 1, 0, 0, 2, 2, 0, 0,  1,  1,  0,  0,  3,  3,
   3 |  0, 2, 1, 1, 0, 3, 2, 2, 0, 2,  1,  1,  0,  4,  3,  3,
   4 |  0, 0, 0, 0, 1, 1, 1, 1, 0, 0,  0,  0,  2,  2,  2,  2,
   5 |  0, 1, 0, 3, 1, 1, 1, 2, 0, 1,  0,  4,  2,  2,  2,  2,
   6 |  0, 0, 2, 2, 1, 1, 1, 1, 0, 0,  3,  3,  2,  2,  2,  2,
   7 |  0, 3, 2, 2, 1, 2, 1, 1, 0, 4,  3,  3,  2,  2,  2,  2,
   8 |  0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  1,  1,  1,  1,  1,  1,
   9 |  0, 1, 0, 2, 0, 1, 0, 4, 1, 1,  1,  2,  1,  1,  1,  3,
  10 |  0, 0, 1, 1, 0, 0, 3, 3, 1, 1,  1,  1,  1,  1,  2,  2,
  11 |  0, 2, 1, 1, 0, 4, 3, 3, 1, 2,  1,  1,  1,  3,  2,  2,
  12 |  0, 0, 0, 0, 2, 2, 2, 2, 1, 1,  1,  1,  1,  1,  1,  1,
  13 |  0, 1, 0, 4, 2, 2, 2, 2, 1, 1,  1,  3,  1,  1,  1,  2,
  14 |  0, 0, 3, 3, 2, 2, 2, 2, 1, 1,  2,  2,  1,  1,  1,  1,
  15 |  0, 4, 3, 3, 2, 2, 2, 2, 1, 3,  2,  2,  1,  2,  1,  1,
etc.

Antti Karttunen, Table of n, a(n) for n = 0..33152; the first 257 antidiagonals, flattened
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel) [(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).]
Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333.
Index entries for sequences related to binary expansion of n

Row/Column 1: A007814, Row/Column 2: A050605, Row/Column 3: A050606. See also A372554 [A(n, 2n+1)].
Cf. A003056, A003987, A004198, A050600, A050601, A048720.
Cf. also A192054.
Cf. also A072030 (A285721) for similar arrays computed for an elementary Euclidean algorithm.

add3c := proc(a,b) option remember; if(0 = ANDnos(a,b)) then RETURN(0); else RETURN(1+add3c(XORnos(a,b),2*ANDnos(a,b))); fi; end;

a[n_, k_] := a[n, k] = If[0 == BitAnd[n, k], 0, 1 + a[BitXor[n, k], 2*BitAnd[n, k]]]; Table[a[n - k, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2014, updated Mar 06 2016 after Maple *)

up_to = 120;
A050602sq(x,y) = if(!bitand(x,y), 0, 1+A050602sq(bitxor(x,y),2*bitand(x,y)));
A050602list(up_to) = { my(v = vector(up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A050602sq(col, a-col))); (v); };
v050602 = A050602list(up_to);
A050602(n) = v050602[1+n]; \\ Antti Karttunen, Sep 04 2023

If A004198(x,y) = 0, then A(x,y) = 0, otherwise A(x,y) = 1 + A(A003987(x,y), 2*A004198(x,y)), where A004198 and A003987 are bitwise-AND and bitwise-XOR respectively.

Name edited by Antti Karttunen, Sep 04 2023

A292244 Base-2 expansion of a(n) encodes the steps where multiples of 3 are encountered when map x -> A253889(x) is iterated down to 1, starting from x=n.

Original entry on oeis.org

0, 0, 1, 0, 0, 3, 0, 2, 5, 0, 0, 1, 0, 0, 1, 12, 6, 7, 14, 0, 1, 0, 4, 1, 8, 10, 3, 0, 0, 21, 24, 0, 1, 28, 2, 3, 2, 0, 1, 0, 0, 5, 2, 2, 1, 22, 24, 17, 0, 12, 33, 32, 14, 35, 42, 28, 45, 24, 0, 1, 16, 2, 11, 48, 0, 59, 0, 8, 3, 0, 2, 5, 0, 16, 1, 4, 20, 3, 6, 6, 7, 8, 0, 1, 56, 0, 3, 0, 42, 5, 0, 48, 5, 0, 0, 1, 14, 2, 65, 64, 56, 49, 44, 4, 49, 64, 6, 57, 0

Offset: 1

Antti Karttunen, Sep 15 2017

			For n = 3, the starting value is a multiple of three, after which follows A253889(3) = 1, the end point of iteration, which is not a multiple of three, thus a(3) = 1*(2^0) = 1.
For n = 8, the starting value is not a multiple of three, after which follows A253889(8) = 3, which is, thus a(8) = 0*(2^0) + 1*(2^1) = 2.
For n = 9, the starting value is a multiple of three, after which follows A253889(9) = 8 (which is not), while A253889(8) = 3 (which is), thus a(9) = 1*(2^0) + 0*(2^1) + 1*(2^2) = 5.

Cf. A048673, A064216, A253889, A291770, A292243, A292247.

Cf. also A292245, A292246, and A292381, A292383, A292385, and A292590, A292591 for similarly constructed sequences, and also A292250.

f[n_] := Times @@ Power[If[# == 1, 1, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger[2 n - 1];g[n_] := (Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n;Table[FromDigits[#, 2] &@ Map[Boole[Divisible[#, 3]] &,  Reverse@ NestWhileList[Floor@ g[Floor[f[#]/2]] &, n, # > 1 &]], {n, 109}] (* Michael De Vlieger, Sep 16 2017 *)

(define (A292244 n) (A291770 (A292243 n)))

a(n) = A291770(A292243(n)).
Other identities. For all n >= 1:
a(A048673(n)) = A292247(n).
a(n) + A292245(n) = A064216(n).
a(n) AND A292245(n) = a(n) AND A292246(n) = 0, where AND is a bitwise-AND (A004198).

A292272 a(n) = n - A048735(n) = n - (n AND floor(n/2)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 16 2017

In binary expansion of n, change those 1's to 0's that have an 1-bit next to them at their left (more significant) side. Only fibbinary numbers (A003714) occur as terms.

			From _Kevin Ryde_, Jun 02 2020: (Start)
     n = 1831 = binary 11100100111
  a(n) = 1060 = binary 10000100100   high 1 of each run
(End)

Antti Karttunen, Table of n, a(n) for n = 0..16383
Index entries for sequences related to binary expansion of n

Cf. A003188, A003714, A003987, A004198, A005940, A048735, A085357, A292371, A292382.

Table[n - BitAnd[n, Floor[n/2]], {n, 0, 93}] (* Michael De Vlieger, Sep 17 2017 *)

a(n) = bitnegimply(n,n>>1); \\ Kevin Ryde, Jun 02 2020

def A292272(n): return n&~(n>>1) # Chai Wah Wu, Jun 29 2022

a(n) = n - A048735(n) = n - (n AND floor(n/2)) = n XOR (n AND floor(n/2)), where AND is bitwise-AND (A004198) and XOR is bitwise-XOR (A003987).
a(n) = n AND A003188(n).
a(n) = A292382(A005940(1+n)).
A059905(a(n)) = A292371(n).
For all n >= 0, A085357(a(n)) = 1.
a(n) = A213064(n) / 2. - Kevin Ryde, Jun 02 2020
a(n) = n AND NOT floor(n/2). - Chai Wah Wu, Jun 29 2022

A255066 The trunk of number-of-runs beanstalk (A255056) with reversed subsections.

Original entry on oeis.org

0, 2, 6, 4, 14, 12, 10, 30, 28, 26, 22, 18, 62, 60, 58, 54, 50, 46, 42, 36, 32, 126, 124, 122, 118, 114, 110, 106, 100, 96, 94, 90, 84, 78, 74, 68, 64, 254, 252, 250, 246, 242, 238, 234, 228, 224, 222, 218, 212, 206, 202, 196, 192, 190, 186, 180, 174, 168, 162, 156, 152, 148, 142, 138, 132, 128, 510

Offset: 0

Antti Karttunen, Feb 14 2015

This can be viewed as an irregular table: after the initial zero on row 0, start each row n with term x = (2^(n+1))-2 and subtract repeatedly the number of runs in binary representation of x to get successive x's, until the number that has already been listed (which is always (2^n)-2) is encountered, which is not listed second time, but instead, the current row is finished [and thus containing only terms of equal binary length, A000523(n) on row n]. The next row then starts with (2^(n+2))-2, with the same process repeated.

			Rows 0 - 5 of the array:
0;
2;
6, 4;
14, 12, 10;
30, 28, 26, 22, 18;
62, 60, 58, 54, 50, 46, 42, 36, 32;
After row 0, the length of row n is given by A255071(n).

Antti Karttunen, Table of n, a(n) for n = 0..16142; Rows 0..16, flattened

Cf. A255067 (same seq, terms divided by 2).
Cf. A255071 (gives row lengths).
Cf. A000523, A004755, A005811, A236840, A255056, A255122.
Analogous sequences: A218616, A230416.

a(0) = 0, a(1) = 2, a(2) = 6; and for n > 2, a(n) = A004755(A004755(A236840(a(n-1)))) if A236840(a(n-1))+2 is power of 2, otherwise just A236840(a(n-1)) [where A004755(x) adds one 1-bit to the left of the most significant bit of x].
In other words, for n > 2, let k = A236840(a(n-1)). Then, if k+2 is not a power of 2, a(n) = k, otherwise a(n) = k + (6 * (2^A000523(k))).
Other identities. For all n >= 0:
a(n) = A255056(A255122(n)).

A269158 Square array A(row,col) = F(row,(2*col)-1), where F(0,q) = F(1,q) = 0, F(2p,q) = F(p,q) XOR A003188(q), F(2p+1,q) = F(q mod 2p+1, 2p+1) XOR (2p+1 AND q). Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 7, 3, 0, 0, 4, 3, 0, 1, 0, 13, 3, 0, 2, 0, 0, 14, 1, 0, 5, 1, 1, 0, 11, 1, 0, 2, 4, 0, 1, 0, 8, 1, 0, 1, 7, 7, 2, 1, 0, 25, 3, 0, 1, 12, 7, 7, 0, 0, 0, 26, 3, 0, 6, 15, 5, 4, 0, 0, 1, 0, 31, 3, 0, 5, 10, 3, 13, 4, 2, 2, 1, 0, 28, 1, 0, 6, 11, 2, 14, 9, 6, 0, 3, 1, 0, 21, 1, 0, 1, 26, 7, 11, 4, 12, 0, 3, 0, 0

Offset: 1

Antti Karttunen, Feb 20 2016

The array gives the values of bivariate function F(p,q) which is well-defined only when q is odd, thus while here its argument p obtains all integer values from 1 onward, argument q gets only odd numbers 1, 3, 5, 7, 9, ... as its values.

Any row n occurs also as row (4^k * n), for all k >= 0.

			The top left [1 .. 16] x [1 .. 25] section of the array:
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  7,  4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
1,  3,  3,  3,  1,  1,  1,  3,  3,  3,  1,  1,  1,  3,  3,  3
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  5,  2,  1,  1,  6,  5,  6,  1,  5,  6,  1,  6,  5,  5
0,  1,  4,  7, 12, 15, 10, 11, 26, 25, 30, 29, 20, 21, 16, 19
1,  0,  7,  7,  5,  3,  2,  7,  2,  1,  5,  3,  1,  4,  5,  4
1,  2,  7,  4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
1,  0,  0,  4,  9,  4,  9,  5, 12,  1,  0,  0, 12,  9,  4,  9
0,  0,  2,  6, 12, 15, 13, 13, 31, 27, 26, 26, 20, 16, 22, 21
1,  2,  0,  0, 13, 11,  7, 11, 14, 13, 14,  3,  8, 10, 10, 15
1,  3,  3,  3,  1,  1,  1,  3,  3,  3,  1,  1,  1,  3,  3,  3
1,  0,  3,  7,  0, 14, 13,  6,  1, 11, 14,  8,  8,  9, 12, 11
0,  2,  0,  3,  8, 13,  9, 15, 27, 27, 26, 31, 20, 18, 22, 20
1,  0,  0,  0, 12,  0, 11, 15,  9,  3, 14, 15,  4,  8,  2, 15
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  7,  3, 13, 15,  0,  8, 17,  8, 17, 11,  8, 14, 18, 10
0,  2,  7,  0,  4, 10,  2, 13, 21, 27, 31, 28, 25, 31, 23, 25
1,  0,  0,  2,  0, 14, 10,  0, 25, 19, 11, 19,  8,  9, 10, 16
1,  2,  5,  2,  1,  1,  6,  5,  6,  1,  5,  6,  1,  6,  5,  5
1,  0,  0,  0,  1, 15, 11, 11,  0, 26, 21, 10, 17, 15, 10, 15
0,  0,  7,  4,  0,  5, 12,  3, 23, 23, 17, 31, 29, 28, 25, 31
1,  2,  3,  4,  1,  0, 13,  8, 26,  0, 31, 23, 13, 19,  8, 11
0,  1,  4,  7, 12, 15, 10, 11, 26, 25, 30, 29, 20, 21, 16, 19
1,  0,  0,  0,  5,  1,  1, 13, 25, 25,  0, 28, 25, 12, 25, 13

Antti Karttunen, Table of n, a(n) for n = 1..32896; the first 256 antidiagonals of the array

Transpose: A269159.
Column 1: Seems to be 0 followed by A039982.
Column 32769: A268819.
Cf. A065621 (occurs as row 2, row 8, and in general, as any row 2^(2n+1) for n >= 0. Seems to be also present as a slanted diagonal F(2n+1,2n-1).)
Cf. A268816 (row 6, row 24, etc.).
Cf. arrays A268829 and A268728 (variants), and also A268931.
Cf. A003188, A003987, A004198.

F[p_, q_] := F[p, q] = Which[p <= 1, 0, p > 1 && OddQ[p], F[Mod[q, p], p] ~BitXor~ BitAnd[p, q], True, F[p/2, q] ~BitXor~ BitXor[q, Floor[q/2]]];
A[n_, k_] := F[n, 2 k - 1];
Table[A[n - k, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 11 2017 *)

(define (A269158 n) (A269158auxbi (A002260 n) (+ -1 (* 2 (A004736 n)))))
;; A269158auxbi can be implemented either as a tail-recursive loop:
(define (A269158auxbi p q) (if (not (odd? q)) (error "A269158bi: the second argument should be odd: " p q) (let loop ((p p) (q q) (s 0)) (cond ((<= p 1) s) ((odd? p) (loop (modulo q p) p (A003987bi s (A004198bi p q)))) (else (loop (/ p 2) q (A003987bi s (A003987bi q (/ (- q 1) 2)))))))))
;; Or a recurrence (reflecting the given recursive formula):
(define (A269158auxbi p q) (cond ((<= p 1) 0) ((even? p) (A003987bi (A269158auxbi (/ p 2) q) (A003188 q))) (else (A003987bi (A269158auxbi (modulo q p) p) (A004198bi p q)))))

A(row,col) = F(row,(2*col)-1), where function F is defined as: If p <= 1, F(p,q) = 0, otherwise if p is an odd number > 1, F(p,q) = F(q mod p, p) XOR (p AND q), otherwise [when p is an even number] F(p,q) = F(p/2,q) XOR A003188(q).

A292245 Base-2 expansion of a(n) encodes the steps where numbers of the form 3k+1 are encountered when map x -> A253889(x) is iterated down to 1, starting from x=n.

Original entry on oeis.org

1, 2, 2, 5, 4, 4, 11, 4, 8, 17, 10, 18, 9, 8, 22, 17, 8, 8, 17, 22, 36, 41, 8, 42, 17, 16, 44, 21, 34, 32, 35, 20, 32, 33, 36, 64, 69, 18, 34, 73, 16, 74, 37, 44, 82, 33, 34, 34, 89, 16, 64, 69, 16, 68, 65, 34, 64, 33, 44, 64, 33, 72, 16, 65, 82, 68, 85, 16, 128, 137, 84, 72, 69, 34, 138, 145, 32, 84, 145, 88, 88, 149, 42, 162, 65, 68, 164, 45, 64

Offset: 1

Antti Karttunen, Sep 15 2017

			For n=1 (the termination value of the iteration), 1 is of the form 3k+1, thus a(1) = 1*(2^0) = 1.
For n=2, 2 is not of the form 3k+1, while A253889(2) = 1 is, thus a(2) = 0*(2^0) + 1*2(^1) = 2.
For n=4, 4 is of the form 3k+1, while A253889(4) = 2 is not, but then A253889(2) = 1 again is, thus a(4) = 1*(2^0) + 0*(2^1) + 1*(2^2) = 5.

Cf. A048673, A064216, A289813, A292243, A292244, A292246, A292248.

f[n_] := Times @@ Power[If[# == 1, 1, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger[2 n - 1]; g[n_] := (Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n; Map[FromDigits[#, 2] &[IntegerDigits[#, 3] /. 2 -> 0] &, Array[a, 98]] (* Michael De Vlieger, Sep 16 2017 *)

a(1) = 1; for n > 1, a(n) = 2*a(A253889(n)) + [n ≡ 1 (mod 3)], where the last part of the formula is Iverson bracket, giving 1 only if n is of the form 3k+1, and 0 otherwise.
a(n) = A289813(A292243(n)).
Other identities. For all n >= 1:
a(A048673(n)) = A292248(n).
a(n) + A292244(n) = A064216(n).
a(n) AND A292244(n) = a(n) AND A292246(n) = 0, where AND is a bitwise-AND (A004198).

A292253 a(1) = 0, a(2) = 1, and for n > 2, a(n) = 2a(A252463(n)) + [n == 1 (mod 2)][J(3|n) == 1], where J is the Jacobi-symbol.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 8, 4, 4, 8, 17, 8, 35, 16, 8, 8, 70, 8, 140, 16, 16, 34, 281, 16, 9, 70, 8, 32, 562, 16, 1124, 16, 32, 140, 17, 16, 2249, 280, 68, 32, 4498, 32, 8996, 68, 16, 562, 17993, 32, 19, 18, 140, 140, 35986, 16, 32, 64, 280, 1124, 71973, 32, 143947, 2248, 32, 32, 64, 64, 287894, 280, 560, 34, 575789, 32, 1151579, 4498, 16, 560, 34, 136, 2303158, 64

Offset: 1

Antti Karttunen, Sep 28 2017

nonn

Base-2 expansion of a(n) encodes the steps where numbers that are either of the form 12k+1 or of the form 12k+11 are encountered when map x -> A252463(x) is iterated down to 1, starting from x=n. An exception is the most significant bit of a(n) which corresponds with the final 1, but is shifted one bit-position towards right.

The AND - XOR formula(s) just restate the fact that J(3|n) = J(-1|n)*J(-3|n), as the Jacobi-symbol is multiplicative (also) with respect to its upper argument.

Cf. A005940, A163511, A243071, A292254, A292255, A292263, A292941, A292943, A292383.

(define (A292253 n) (if (<= n 2) (- n 1) (+ (if (and (odd? n) (= 1 (jacobi-symbol 3 n))) 1 0) (* 2 (A292253 (A252463 n))))))

a(1) = 0, a(2) = 1, and for n > 2, a(n) = 2*a(A252463(n)) + [n == 1 (mod 2)]*[J(3|n) == 1], where J is the Jacobi-symbol, and [ ]'s are Iverson brackets, whose product gives 1 only if n is an odd number for which J(3|n) = +1, and 0 otherwise.
a(n) = A292263(n) AND (A292383(n) XOR A292941(n)), where AND is bitwise-and (A004198) and XOR is bitwise-XOR (A003987). [See comments.]
For n >= 0, a(A163511(n)) = A292254(n).
For n >= 1, a(n) + A292255(n) + A292943(n) = A243071(n).

cp's OEIS Frontend

A075173 Prime factorization of n encoded by interleaving successive prime exponents in unary to bit-positions given by columns of A075300.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A292592 a(n) = A292590(A245612(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A292944 a(n) = A292272(A004754(n)) - 2*A053644(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A050602 Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A292244 Base-2 expansion of a(n) encodes the steps where multiples of 3 are encountered when map x -> A253889(x) is iterated down to 1, starting from x=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A292272 a(n) = n - A048735(n) = n - (n AND floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A255066 The trunk of number-of-runs beanstalk (A255056) with reversed subsections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A269158 Square array A(row,col) = F(row,(2*col)-1), where F(0,q) = F(1,q) = 0, F(2p,q) = F(p,q) XOR A003188(q), F(2p+1,q) = F(q mod 2p+1, 2p+1) XOR (2p+1 AND q). Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

A292253 a(1) = 0, a(2) = 1, and for n > 2, a(n) = 2a(A252463(n)) + [n == 1 (mod 2)][J(3|n) == 1], where J is the Jacobi-symbol.