A115872 -id:A115872 - cp's OEIS frontend

A115873 First column of A115872.

1, 1, 3, 1, 7, 3, 7, 1, 15, 7, 3, 3, 5, 7, 15, 1, 31, 15, 7, 7, 31, 3, 7, 3, 31, 5, 31, 7, 31, 15, 31, 1, 63, 31, 15, 15, 7, 7, 7, 7, 63, 31, 3, 3, 63, 7, 15, 3, 21, 31, 63, 5, 63, 31, 7, 7, 9, 31, 63, 15, 21, 31, 63, 1, 127, 63, 31, 31, 15, 15, 15, 15, 127, 7, 31, 7, 15, 7, 15, 7, 51

Offset: 1

Antti Karttunen, Feb 07 2006

nonn

Cf. A114395, A114396, A115872.

X[a_, b_] := Module[{A, B, C, x},
   A = Reverse@IntegerDigits[a, 2];
   B = Reverse@IntegerDigits[b, 2];
   C = Expand[
      Sum[A[[i]]*x^(i - 1), {i, 1, Length[A]}]*
      Sum[B[[i]]*x^(i - 1), {i, 1, Length[B]}]];
   PolynomialMod[C, 2] /. x -> 2];
T[n_, k_] := Module[{x = BitXor[n - 1, 2 n - 1], k0 = k},
     For[i = 1, True, i++, If[n*i == X[x, i],
     If[k0 == 1, Return[i], k0--]]]];
a[n_] := T[n, 1];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 04 2022 *)

a(2^k) = 1, a(2n) = a(n).

A114388 Transpose of table A115872.

Original entry on oeis.org

1, 1, 2, 3, 2, 3, 1, 6, 3, 4, 7, 2, 7, 4, 5, 3, 14, 3, 12, 5, 6, 7, 6, 15, 4, 14, 6, 7, 1, 14, 7, 28, 5, 15, 7, 8, 15, 2, 15, 12, 30, 6, 24, 8, 9, 7, 30, 3, 28, 14, 31, 7, 28, 9, 10, 3, 14, 31, 4, 30, 15, 56, 8, 30, 10, 11, 3, 6, 15, 60, 5, 31, 24, 60, 9, 31, 11, 12, 5, 6, 12, 28, 62, 6

Offset: 1

Antti Karttunen, Feb 07 2006

Cf. A115872.

First row: A115873.

X[a_, b_] := Module[{A, B, C, x},
     A = Reverse@IntegerDigits[a, 2];
     B = Reverse@IntegerDigits[b, 2];
     C = Expand[
        Sum[A[[i]]*x^(i - 1), {i, 1, Length[A]}]*
        Sum[B[[i]]*x^(i - 1), {i, 1, Length[B]}]];
     PolynomialMod[C, 2] /. x -> 2];
S[n_, k_] := Module[{x = BitXor[n - 1, 2 n - 1], k0 = k},
     For[i = 1, True, i++,If[n*i == X[x, i],
     If[k0 == 1, Return[i], k0--]]]];
T[n_, k_] := S[k, n];
Table[T[n - k + 1, k], {n, 1, 14}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 04 2022 *)

A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 4, 3, 0, 0, 4, 6, 6, 4, 0, 0, 5, 8, 5, 8, 5, 0, 0, 6, 10, 12, 12, 10, 6, 0, 0, 7, 12, 15, 16, 15, 12, 7, 0, 0, 8, 14, 10, 20, 20, 10, 14, 8, 0, 0, 9, 16, 9, 24, 17, 24, 9, 16, 9, 0, 0, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 0, 0, 11, 20, 27, 32, 27, 20, 27, 32, 27, 20, 11, 0

Offset: 0

Antti Karttunen, Apr 26 1999

Essentially same as A091257 but computed starting from offset 0 instead of 1.
Each polynomial in GF(2)[X] is encoded as the number whose binary representation is given by the coefficients of the polynomial, e.g., 13 = 2^3 + 2^2 + 2^0 = 1101_2 encodes 1*X^3 + 1*X^2 + 0*X^1 + 1*X^0 = X^3 + X^2 + X^0. - Antti Karttunen and Peter Munn, Jan 22 2021
To listen to this sequence, I find instrument 99 (crystal) works well with the other parameters defaulted. - Peter Munn, Nov 01 2022

			Top left corner of array:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 ...
  0  3  6  5 12 15 10  9 24 27 30 29 20 23 18 17 ...
  ...
From _Antti Karttunen_ and _Peter Munn_, Jan 23 2021: (Start)
Multiplying 10 (= 1010_2) and 11 (= 1011_2), in binary results in:
     1011
  *  1010
  -------
   c1011
  1011
  -------
  1101110  (110 in decimal),
and we see that there is a carry-bit (marked c) affecting the result.
In carryless binary multiplication, the second part of the process (in which the intermediate results are summed) looks like this:
    1011
  1011
  -------
  1001110  (78 in decimal).
(End)

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Antti Karttunen, Scheme-program for computing this sequence.
N. J. A. Sloane, Transforms: Maple implementation of binary eXclusive OR (XORnos).
Index entries for sequences related to carryless arithmetic
Index entries for sequences related to polynomials in ring GF(2)[X]

Cf. A051776 (Nim-product), A091257 (subtable).
Carryless multiplication in other bases: A325820 (3), A059692 (10).
Ordinary {0..i} * {0..j} multiplication table: A004247 and its differences from this: A061858 (which lists further sequences related to presence/absence of carry in binary multiplication).
Carryless product of the prime factors of n: A234741.
Binary irreducible polynomials ("X-primes"): A014580, factorization table: A256170, table of "X-powers": A048723, powers of 3: A001317, rearranged subtable with distinct terms (comparable to A054582): A277820.
See A014580 for further sequences related to the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the integer encoding.
Row/column 3: A048724 (even bisection of A003188), 5: A048725, 6: A048726, 7: A048727; main diagonal: A000695.
Associated additive operation: A003987.
Equivalent sequences, as compared with standard integer multiplication: A048631 (factorials), A091242 (composites), A091255 (gcd), A091256 (lcm), A280500 (division).
See A091202 (and its variants) and A278233 for maps from/to ordinary multiplication.
See A115871, A115872 and A277320 for tables related to cross-domain congruences.

trinv := n -> floor((1+sqrt(1+8*n))/2); # Gives integral inverses of the triangular numbers
# Binary multiplication of nn and mm, but without carries (use XOR instead of ADD):
Xmult := proc(nn,mm) local n,m,s; n := nn; m := mm; s := 0; while (n > 0) do if(1 = (n mod 2)) then s := XORnos(s,m); fi; n := floor(n/2); # Shift n right one bit. m := m*2; # Shift m left one bit. od; RETURN(s); end;

trinv[n_] := Floor[(1 + Sqrt[1 + 8*n])/2];
Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; Return[s]];
a[n_] := Xmult[(trinv[n] - 1)*((1/2)*trinv[n] + 1) - n, n - (trinv[n]*(trinv[n] - 1))/2];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 16 2015, updated Mar 06 2016 after Maple *)

up_to = 104;
A048720sq(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A048720list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A048720sq(col, a-col))); (v); };
v048720 = A048720list(up_to);
A048720(n) = v048720[1+n]; \\ Antti Karttunen, Feb 15 2021

a(n) = Xmult( (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n), (n-((trinv(n)*(trinv(n)-1))/2)) );
T(2b, c)=T(c, 2b)=T(b, 2c)=2T(b, c); T(2b+1, c)=T(c, 2b+1)=2T(b, c) XOR c - Henry Bottomley, Mar 16 2001
For n >= 0, A003188(2n) = T(n, 3); A003188(2n+1) = T(n, 3) XOR 1, where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Feb 11 2021

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

Original entry on oeis.org

1, 2, 7, 4, 13, 14, 11, 8, 25, 26, 31, 28, 21, 22, 19, 16, 49, 50, 55, 52, 61, 62, 59, 56, 41, 42, 47, 44, 37, 38, 35, 32, 97, 98, 103, 100, 109, 110, 107, 104, 121, 122, 127, 124, 117, 118, 115, 112, 81, 82, 87, 84, 93, 94, 91, 88, 73, 74, 79, 76, 69, 70, 67, 64, 193

Offset: 1

Marc LeBrun, Nov 07 2001

a(0)=0. The alternation is applied only to the nonzero bits and does not depend on the exponent of two. All integers have a unique reversing binary representation (see cited exercise for proof). Complement of A048724.
A permutation of the "odious" numbers A000069.
Write n-1 and 2n-1 in binary and add them mod 2; example: n = 6, n-1 = 5 = 101 in binary, 2n-1 = 11 = 1011 in binary and their sum is 1110 = 14, so a(6) = 14. - Philippe Deléham, Apr 29 2005
As already pointed out, this is a permutation of the odious numbers A000069 and A010060(A000069(n)) = 1, so A010060(a(n)) = 1; and A010060(A048724(n)) = 0. - Philippe Deléham, Apr 29 2005. Also a(n) = A000069(A003188(n - 1)).

			a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192

Cf. A003188, A065620, A048724, A072219, A073122.
Differs from A115857 for the first time at n=19, where a(19)=55, while A115857(19)=23. Cf. A104895, A115872, A114389, A114390, A105081.
Cf. A245471.

import Data.Bits (xor, (.&.))
a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
-- Reinhard Zumkeller, Mar 26 2014

f[n_] := BitXor[n, 2 n + 1]; Array[f, 60, 0] (* Robert G. Wilson v, Jun 09 2010 *)

a(n)=if(n<2,1,if(n%2==0,2*a(n/2),2*a((n+1)/2)-2*(-1)^((n-1)/2)+1))

def a(n): return n^(2*(n - (n & -n))) # Indranil Ghosh, Jun 04 2017

def A065621(n): return n^ (n&~-n)<<1 # Chai Wah Wu, Jun 29 2022

a(n) = if n=0 or n=1 then n else b+2*a(b+(1-2*b)*n)/2) where b is the least significant bit in n.
a(n) = n XOR 2 (n - (n AND -n)).
a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2*a(n+1) - 2(-1)^n + 1. - Ralf Stephan, Aug 20 2003
a(n) = A048724(n-1) - (-1)^n. - Ralf Stephan, Sep 10 2003
a(n) = Sum_{k=0..n} (1-(-1)^round(-n/2^k))/2*2^k. - Benoit Cloitre, Apr 27 2005
Closely related to Gray codes in another way: a(n) = 2 * A003188(n-1) + (n mod 2); a(n) = 4 * A003188((n-1) div 2) + (n mod 4). - Matt Erbst (matt(AT)erbst.org), Jul 18 2006 [corrected by Peter Munn, Jan 30 2021]
a(n) = n XOR 2(n AND NOT -n). - Chai Wah Wu, Jun 29 2022
a(n) = A003188(2n-1). - Friedjof Tellkamp, Jan 18 2024

More terms from Ralf Stephan, Sep 08 2003

A234742 Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.

Original entry on oeis.org

0, 1, 2, 3, 4, 9, 6, 7, 8, 21, 18, 11, 12, 13, 14, 27, 16, 81, 42, 19, 36, 49, 22, 39, 24, 25, 26, 63, 28, 33, 54, 31, 32, 93, 162, 91, 84, 37, 38, 99, 72, 41, 98, 75, 44, 189, 78, 47, 48, 77, 50, 243, 52, 57, 126, 55, 56, 117, 66, 59, 108, 61, 62, 147, 64, 441

Offset: 0

Antti Karttunen, Jan 22 2014

"Product" refers to the ordinary multiplication of integers.
Differs from A235042 and A236837 for the first time at n=25, where a(n)=25, while A235042(25)=5 and A236837(25)=0. Thus A234741(A234742(n)) = n up to n=24.
a(n) >= n. [All terms of the table A061858 are nonnegative as the product of multiplying two numbers with carries is never less than when multiplying them without carries.]
Specifically, for all n, a(A091209(n)) > A091209(n).
a(A091209(n)) is always composite and, by the above inequality, larger than A091209(n), which implies that none of the terms of A091209 occur in this sequence. Cf. also A236844.
Starting with various terms (primes) in A235033 and iterating the map A234742, we get 5 -> 9 -> 21 -> 49 -> 77 -> 177 -> 333 = a(333).
Another example: 17 -> 81 -> 169 -> 309 -> 721 = a(721).
Does every chain of such iterations eventually reach a fixed point? (One of the terms of A235035.) Or do some of them manage to avoid such "traps" indefinitely? (Note how the terms of A235035 seem to get rarer, but only rather slowly.)
Starting from 23, we get the sequence: 23, 39, 99, 279, 775, 1271, 3003, 26411, 45059, ... which reaches its fixed point, 3643749709604450870616156947649219, after 55 iterations. - M. F. Hasler, Feb 18 2014. [This is now sequence A244323. See also A260729, A260735 and A260441.] - Antti Karttunen, Aug 05 2015
Note also that when coming backwards from some term of such a chain by iterating A234741, we may not necessarily end at the same term we started from.

			3 has binary representation '11', which encodes the polynomial X + 1, which is irreducible in GF(2)[X], so the result is just a(3)=3.
5 has binary representation '101' which encodes the polynomial X^2 + 1, which is reducible in the polynomial ring GF(2)[X], factoring as (X+1)(X+1), i.e., 5 = A048720(3,3), as 3 ('11' in binary) encodes the polynomial (X+1), irreducible in GF(2)[X]. 3*3 = 9, thus a(5)=9.
9 has binary representation '1001', which encodes the polynomial X^3 + 1, which factors (in GF(2)[X]!) as (X+1)(X^2+X+1), i.e., 9 = A048720(3,7) (7, '111' in binary, encodes the other factor polynomial X^2+X+1). 3*7 = 21, thus a(9)=21.
25 has binary representation '11001', which encodes the polynomial X^4 + X^3 + 1, which is irreducible in GF(2)[X], so the result is just a(25)=25.

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

A235035 gives the k for which a(k)=k.
A236853(n) gives the number of times n occurs in this sequence.
A236842 gives the same sequence sorted and with duplicates removed, A236844 gives the numbers that do not occur here, A236845 gives numbers that occur more than once, A236846 the least inverse and A236847 the greatest inverse. A236850 gives such k that a(k) = A236837(k).
Cf. A014580, A048720, A234741, A236379, A236837, A236851 & A236852, A115857, A115872.
Cf. also A260712, A260713, A260716 and A244323, A260729, A260735, A260441 (iterations starting from various terms of A236844).

A234742(n)=factorback(subst(lift(factor(Mod(1,2)*Pol(binary(n)))),x,2)) \\ M. F. Hasler, Feb 18 2014, corrected Andrew Howroyd, Aug 01 2018

To compute a(n): factor the polynomial over GF(2) encoded by n, into its irreducible factors; in other words, find a unique multiset of terms i, j, ..., k (not necessarily distinct) from A014580 for which i x j x ... x k = n, where x stands for the carryless multiplication A048720. Then a(n) = i*j*...*k is the product of those terms with ordinary multiplication. Because of the effect of the carry-bits in the latter, the result is always greater than or equal to n, so we have a(n) >= n for all n.
a(2n) = 2*a(n).
a(A235035(n)) = A235035(n).
A236379(n) = a(n) - n.
For all n, a(n) >= A236837(n).

A277320 Square array A(r,c) = A048720(A065621(r), c), read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Original entry on oeis.org

1, 2, 2, 3, 4, 7, 4, 6, 14, 4, 5, 8, 9, 8, 13, 6, 10, 28, 12, 26, 14, 7, 12, 27, 16, 23, 28, 11, 8, 14, 18, 20, 52, 18, 22, 8, 9, 16, 21, 24, 57, 56, 29, 16, 25, 10, 18, 56, 28, 46, 54, 44, 24, 50, 26, 11, 20, 63, 32, 35, 36, 39, 32, 43, 52, 31, 12, 22, 54, 36, 104, 42, 58, 40, 100, 46, 62, 28, 13, 24, 49, 40, 101, 112, 49, 48, 125, 104, 33, 56, 21

Offset: 1

Antti Karttunen, Nov 01 2016

			The top left corner of the array:
   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12
   2,   4,   6,   8,  10,  12,  14,  16,  18,  20,  22,  24
   7,  14,   9,  28,  27,  18,  21,  56,  63,  54,  49,  36
   4,   8,  12,  16,  20,  24,  28,  32,  36,  40,  44,  48
  13,  26,  23,  52,  57,  46,  35, 104, 101, 114, 127,  92
  14,  28,  18,  56,  54,  36,  42, 112, 126, 108,  98,  72
  11,  22,  29,  44,  39,  58,  49,  88,  83,  78,  69, 116
   8,  16,  24,  32,  40,  48,  56,  64,  72,  80,  88,  96
  25,  50,  43, 100, 125,  86,  79, 200, 209, 250, 227, 172
  26,  52,  46, 104, 114,  92,  70, 208, 202, 228, 254, 184
  31,  62,  33, 124,  99,  66,  93, 248, 231, 198, 217, 132
  28,  56,  36, 112, 108,  72,  84, 224, 252, 216, 196, 144
  21,  42,  63,  84,  65, 126, 107, 168, 189, 130, 151, 252
  22,  44,  58,  88,  78, 116,  98, 176, 166, 156, 138, 232
  19,  38,  53,  76,  95, 106, 121, 152, 139, 190, 173, 212
  16,  32,  48,  64,  80,  96, 112, 128, 144, 160, 176, 192
  49,  98,  83, 196, 245, 166, 151, 392, 441, 490, 475, 332
  50, 100,  86, 200, 250, 172, 158, 400, 418, 500, 454, 344
  55, 110,  89, 220, 235, 178, 133, 440, 399, 470, 481, 356

Transpose: A277199.
Main diagonal: A277699.
Row 1: A000027, Row 3: A048727.
Column 1: A065621, Column 3: A277823, Column 5: A277825.
Cf. A277820 (array obtained by selecting only the columns with an index A001317(k), k=0..).
Cf. A048720, A115872.

(define (A277320 n) (A277320bi (A002260 n) (A004736 n)))
(define (A277320bi row col) (A048720bi (A065621 row) col))

A(r,c) = A048720(A065621(r), c).

A235041 Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.

Original entry on oeis.org

0, 1, 2, 3, 4, 25, 6, 7, 8, 5, 50, 11, 12, 13, 14, 43, 16, 55, 10, 19, 100, 9, 22, 87, 24, 321, 26, 15, 28, 91, 86, 31, 32, 29, 110, 79, 20, 37, 38, 23, 200, 41, 18, 115, 44, 125, 174, 47, 48, 21, 642, 89, 52, 117, 30, 227, 56, 53, 182, 59, 172, 61, 62, 27, 64

Offset: 0

Antti Karttunen, Jan 02 2014

nonn

Like A091202 this is a factorization-preserving isomorphism from integers to GF(2)[X]-polynomials. The latter are encoded in the binary representation of n like this: n=11, '1011' in binary, stands for polynomial x^3+x+1, n=25, '11001' in binary, stands for polynomial x^4+x^3+1. However, this version does not map the primes (A000040) straight to the irreducible GF(2)[X] polynomials (A014580), but instead fixes the intersection of those two sets (A091206), and maps the elements in their set-wise difference A000040 \ A014580 (= A091209) in numerical order to the set-wise difference A014580 \ A000040 (= A091214).
The composite values are defined by the multiplicativity. E.g., we have a(3n) = A048724(a(n)) and a(3^n) = A001317(n) for all n.
This map satisfies many of the same identities as A091202, e.g., we have A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)) and A008683(n) = A091219(a(n)) for all n >= 1.

			Here (t X u) = A048720(t,u):
a(2)=2, a(3)=3 and a(7)=7, as 2, 3 and 7 are all in A091206.
a(4) = a(2*2) = a(2) X a(2) = 2 X 2 = 4.
a(9) = a(3*3) = a(3) X a(3) = 3 X 3 = 5.
a(5) = 25, as 5 is the first term of A091209 and 25 is the first term of A091214.
a(10) = a(2*5) = a(2) X a(5) = 2 X 25 = 50.
Similarly, a(17) = 55, as 17 is the second term of A091209 and 55 is the second term of A091214.
a(21) = a(3*7) = a(3) X a(7) = 3 X 7 = 9.

Inverse: A235042. Fixed points: A235045.
Cf. A010051, A048720, A091225, A091214, A235043, A048724, A115857, A115872.
Similar cross-multiplicative permutations: A091202, A091204, A106442, A106444, A106446.

a(0)=0, a(1)=1, a(p) = p for those primes p whose binary representations encode also irreducible GF(2)[X]-polynomials (i.e., p is in A091206), and for the rest of the primes q (those whose binary representation encode composite GF(2)[X]-polynomials, i.e., q is in A091209), a(q) = A091214(A235043(q)), and for composite natural numbers, a(p * q * r * ...) = a(p) X a(q) X a(r) X ..., where p, q, r, ... are primes and X stands for the carryless multiplication (A048720) of GF(2)[X] polynomials encoded as explained in the Comments section.

A325567 a(1) = 1; for n > 1, a(n) is the largest proper divisor d of n such that A048720(A065621(d),n/d) is equal to n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 4, 3, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 11, 2, 5, 12, 1, 2, 1, 8, 1, 6, 1, 4, 3, 2, 1, 16, 7, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 13, 22, 1, 4, 1, 10, 1, 24, 1, 2, 5, 4, 1, 2, 1, 16, 1, 2, 1, 12, 1, 2, 1, 8, 1, 6, 1, 4, 3, 2, 1, 32, 1, 14, 1, 4, 1, 2, 1, 8, 7

Offset: 1

Antti Karttunen, May 09 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16383
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A032742, A048720, A065621, A115872, A325565, A325566, A325568.

A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A065621(n) = bitxor(n-1,n+n-1);
A325567(n) = if(1==n,n,fordiv(n,d,if((d>1)&&A048720(A065621(n/d),d)==n,return(n/d))));

A325565 a(n) is the number of such divisors d of n that A048720(A065621(d),n/d) is equal to n.

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 1, 4, 2, 2, 1, 3, 1, 2, 1, 5, 1, 4, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 2, 2, 2, 6, 1, 2, 1, 4, 1, 4, 1, 3, 2, 2, 1, 5, 2, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 2, 4, 1, 3, 1, 4, 1, 8, 1, 2, 2, 3, 1, 2, 1, 5, 1, 2, 1, 6, 1, 2, 1, 4, 1, 4, 1, 3, 2, 2, 1, 6, 1, 4, 1, 3, 1, 2, 1, 4, 2

Offset: 1

Antti Karttunen, May 09 2019

nonn

Equally, a(n) is number of such pairs of natural numbers t, u that A048720(t,u) = n and A065620(t)*u = n.

Cf. A000005, A000265, A001511, A048720, A065620, A065621, A091220, A115872, A325566, A325567, A325568, A325569, A325570 (positions of ones).

A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A065621(n) = bitxor(n-1,n+n-1);
A325565(n) = sumdiv(n,d,A048720(A065621(d),n/d)==n);

A065620(n, c=1) = sum(i=0, logint(n+!n, 2), if(bittest(n, i), (-1)^c++<A065620
A325565(n) = { my(p = Pol(binary(n))*Mod(1, 2)); sum(d=1,n,my(q = Pol(binary(d))*Mod(1, 2)); (0==(p%q) && (n==(A065620(d)*fromdigits(Vec(lift(p/q)),2))))); };

a(n) = Sum_{d|n} [A048720(A065621(d),n/d) == n], where [ ] is the Iverson bracket.
a(n) / a(A000265(n)) = A001511(n).
a(n) <= A000005(n) for all n.
a(n) <= A091220(n) for all n.

A115857 Smallest integer m > n, such that there exists nonzero solutions to a cross-domain congruence n*i = m X i, n if no such integer exists.

Original entry on oeis.org

1, 2, 7, 4, 13, 14, 11, 8, 25, 26, 31, 28, 21, 22, 19, 16, 49, 50, 23, 52, 29, 62, 47, 56, 41, 42, 31, 44, 37, 38, 35, 32, 97, 98, 39, 100, 61, 46, 63, 104, 105, 58, 59, 124, 53, 94, 55, 112, 81, 82, 55, 84, 93, 62, 59, 88, 73, 74, 63, 76, 69, 70, 67, 64, 193, 194, 71, 196, 77

Offset: 1

Antti Karttunen, Feb 07 2006

nonn

Here * stands for ordinary multiplication and X means carryless (GF(2)[X]) multiplication (A048720).

Index entries for sequences defined by congruent products between domains N and GF(2)[X]

a(2n) = 2*a(n). Bisection A115858 gives only the odd terms. Differs from A065621 for the first time at n=19, where a(19)=23, while A065621(19)=55. The next differences are a(21)=29 (A065621(21)=61) and a(23)=47 (A065621(23)=59). Cf. A115859, A115861, A115869, A115871, A115872.

cp's OEIS Frontend

A115873 First column of A115872.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A114388 Transpose of table A115872.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A048720 Multiplication table {0..i} X {0..j} of binary polynomials (polynomials over GF(2)) interpreted as binary vectors, then written in base 10; or, binary multiplication without carries.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

A234742 Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A277320 Square array A(r,c) = A048720(A065621(r), c), read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

Formula

A235041 Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A325567 a(1) = 1; for n > 1, a(n) is the largest proper divisor d of n such that A048720(A065621(d),n/d) is equal to n.

Views

Author

Keywords