A115872 Square array where row n gives all solutions k > 0 to the cross-domain congruence n*k = A048720(A065621(n),k), zero sequence (A000004) if no such solutions exist.

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

Offset: 1

Author

Antti Karttunen, Feb 07 2006

Keywords

• nonn
• tabl

Comments

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

Square 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), etc.

Rows at positions 2^k are 1, 2, 3, ..., (A000027). Row 2n is equal to row n.

Numbers on each row give a subset of positions of zeros at the corresponding row of A284270. - Antti Karttunen, May 08 2019

Examples

			Fifteen initial terms of rows 1 - 19 are listed below:
   1:  1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15, ...
   2:  1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15, ...
   3:  3,  6,  7,  12,  14,  15,  24,  28,  30,  31,  48,  51,  56,  60,  62, ...
   4:  1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15, ...
   5:  7, 14, 15,  28,  30,  31,  56,  60,  62,  63, 112, 120, 124, 126, 127, ...
   6:  3,  6,  7,  12,  14,  15,  24,  28,  30,  31,  48,  51,  56,  60,  62, ...
   7:  7, 14, 15,  28,  30,  31,  56,  60,  62,  63, 112, 120, 124, 126, 127, ...
   8:  1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15, ...
   9: 15, 30, 31,  60,  62,  63, 120, 124, 126, 127, 240, 248, 252, 254, 255, ...
  10:  7, 14, 15,  28,  30,  31,  56,  60,  62,  63, 112, 120, 124, 126, 127, ...
  11:  3,  6, 12,  15,  24,  27,  30,  31,  48,  51,  54,  60,  62,  63,  96, ...
  12:  3,  6,  7,  12,  14,  15,  24,  28,  30,  31,  48,  51,  56,  60,  62, ...
  13:  5, 10, 15,  20,  21,  30,  31,  40,  42,  45,  47,  60,  61,  62,  63, ...
  14:  7, 14, 15,  28,  30,  31,  56,  60,  62,  63, 112, 120, 124, 126, 127, ...
  15: 15, 30, 31,  60,  62,  63, 120, 124, 126, 127, 240, 248, 252, 254, 255, ...
  16:  1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15, ...
  17: 31, 62, 63, 124, 126, 127, 248, 252, 254, 255, 496, 504, 508, 510, 511, ...
  18: 15, 30, 31,  60,  62,  63, 120, 124, 126, 127, 240, 248, 252, 254, 255, ...
  19:  7, 14, 28,  31,  56,  62,  63, 112, 119, 124, 126, 127, 224, 238, 248, ...
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of array
• Index entries for sequences defined by congruent products between domains N and GF(2)[X]

Crossrefs

Transpose: A114388. First column: A115873.

Cf. A048720, A065621, A115857, A115871, A325565, A325566, A325567, A325568, A325570, A325571.

Cf. also arrays A277320, A277810, A277820, A284270.

A few odd-positioned rows: row 1: A000027, Row 3: A048717, Row 5: A115770 (? Checked for all values less than 2^20), Row 7: A115770, Row 9: A115801, Row 11: A115803, Row 13: A115772, Row 15: A115801 (? Checked for all values less than 2^20), Row 17: A115809, Row 19: A115874, Row 49: A114384, Row 57: A114386.

Programs

Mathematica

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, 2n-1], k0 = k},
     For[i = 1, True, i++, If[n*i == X[x, i],
     If[k0 == 1, Return[i], k0--]]]];
Table[T[n-k+1, k], {n, 1, 14}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 04 2022 *)

PARI

up_to = 120;
A048720(b,c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A065621(n) = bitxor(n-1,n+n-1);
A115872sq(n, k) = { my(x = A065621(n)); for(i=1,oo,if((n*i)==A048720(x,i),if(1==k,return(i),k--))); };
A115872list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A115872sq(col,(a-(col-1))))); (v); };
v115872 = A115872list(up_to);
A115872(n) = v115872[n]; \\ (Slow) - Antti Karttunen, May 08 2019

Extensions

Example section added and the data section extended up to n=105 by Antti Karttunen, May 08 2019