A048717 -id:A048717 - cp's OEIS frontend

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

Antti Karttunen, Feb 07 2006

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

			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, ...

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.

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 *)

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

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

A048715 Binary expansion matches (100(0))(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

Original entry on oeis.org

0, 1, 2, 4, 8, 9, 16, 17, 18, 32, 33, 34, 36, 64, 65, 66, 68, 72, 73, 128, 129, 130, 132, 136, 137, 144, 145, 146, 256, 257, 258, 260, 264, 265, 272, 273, 274, 288, 289, 290, 292, 512, 513, 514, 516, 520, 521, 528, 529, 530, 544, 545, 546, 548, 576, 577, 578, 580

Offset: 0

Antti Karttunen, Mar 30 1999

No more than one 1-bit in each bit triple.
All terms satisfy A048727(n) = 7*n.
Constructed from A000930 in the same way as A003714 is constructed from A000045.
It appears that n is in the sequence if and only if C(7n,n) is odd (cf. A003714). - Benoit Cloitre, Mar 09 2003
The conjecture by Benoit is correct. This is easily proved using the well-known result that the multiplicity with which a prime p divides C(n+m,n) is the number of carries when adding n+m in base p. - Franklin T. Adams-Watters, Oct 06 2009
Appears to be the set of numbers x such that (x AND 5*x) = x and (x OR 3*x)/x = 3. - Gary Detlefs, Jun 08 2024

G. C. Greubel, Table of n, a(n) for n = 0..1275
Sebastian Karlsson, Walnut code that verifies the conjectures of Paul D. Hanna
Walnut can be downloaded from https://cs.uwaterloo.ca/~shallit/walnut.html.
Index entries for sequences defined by congruent products between domains N and GF(2)[X]
Index entries for sequences defined by congruent products under XOR
Index entries for 2-automatic sequences.

Subsequence of A048716.

Cf. A003726, A004742, A004743, A004744, A048717, A048718, A048719, A048730, A048733, A115422, A115423, A115424.

Reap[Do[If[OddQ[Binomial[7n, n]], Sow[n]], {n, 0, 400}]][[2, 1]]
(* Second program: *)
filterQ[n_] := With[{bb = IntegerDigits[n, 2]}, !MatchQ[bb, {_, 1, 0, 1, _}|{_, 1, 1, _}]];
Select[Range[0, 580], filterQ] (* Jean-François Alcover, Dec 31 2020 *)

is(n)=!bitand(n, 6*n) \\ Charles R Greathouse IV, Oct 03 2016

for my $k (0..580) { print "$k, " if sprintf("%b", $k) =~ m{^(100(0)*)*(0|1|10)?$}; } # Georg Fischer, Jun 26 2021

import re
def ok(n): return re.fullmatch('(100(0)*)*(0|1|10)?', bin(n)[2:]) != None
print(list(filter(ok, range(581)))) # Michael S. Branicky, Jun 26 2021

a(0) = 0, a(n) = (2^(invfoo(n)-1))+a(n-foo(invfoo(n))), where foo(n) is foo(n-1) + foo(n-3) (A000930) and invfoo is its "integral" (floored down) inverse.
a(n) XOR 6*a(n) = 7*a(n); 3*a(n) XOR 4*a(n) = 7*a(n); 3*a(n) XOR 5*a(n) = 6*a(n); (conjectures). - Paul D. Hanna, Jan 22 2006
The conjectures can be verified using the Walnut theorem-prover (see links). - Sebastian Karlsson, Dec 31 2022

Definition corrected by Georg Fischer, Jun 26 2021

A048719 Binary expansion matches ((0)0011)(0*).

Original entry on oeis.org

0, 3, 6, 12, 24, 48, 51, 96, 99, 102, 192, 195, 198, 204, 384, 387, 390, 396, 408, 768, 771, 774, 780, 792, 816, 819, 1536, 1539, 1542, 1548, 1560, 1584, 1587, 1632, 1635, 1638, 3072, 3075, 3078, 3084, 3096

Offset: 0

Antti Karttunen, Mar 30 1999

1-bits occur only in pairs, separated from other such pairs by at least two 0-bits.

All terms satisfy both A048727(n) = 3*n and A048725(n) = 5*n.

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

Intersection of A048716 and A048717.

filterQ[n_] := With[{bb = IntegerDigits[n, 2]}, !MatchQ[bb, {1}|{1, 0, _}|{_, 0, 1}|{_, 0, 1, 0, _}|{_, 1, 1, 1, _}|{_, 1, 0, 1, _}]];
Select[Range[0, 3096], filterQ] (* Jean-François Alcover, Dec 31 2020 *)

is(n)=n%3==0 && !bitand(n/3, 14*n/3) \\ Charles R Greathouse IV, Oct 03 2016

a(n) = 3*A048718(n).

A115772 Integers i such that 13*i = A048720bi(21,i).

Original entry on oeis.org

0, 5, 10, 15, 20, 21, 30, 31, 40, 42, 45, 47, 60, 61, 62, 63, 80, 84, 85, 90, 94, 95, 120, 122, 124, 125, 126, 127, 160, 165, 168, 170, 173, 175, 180, 181, 188, 189, 190, 191, 240, 244, 245, 248, 250, 252, 253, 254, 255, 320, 330, 336, 340, 341, 346, 350, 351

Offset: 0

Antti Karttunen, Jan 30 2006

nonn

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

a(n) appears to be the set of all n that can be expressed as x OR 4x for the bitwise OR operation. [From Gary Detlefs Dec 20 2010]

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

Row 13 of A115872. Cf. A048717, A115767, A115770. Superset of A115774 ? A115776 gives the terms which are not in A115774. A115773 shows this sequence in binary.

Cf. A178891

A115774 Integers i such that 15*i = A048720bi(23,i).

Original entry on oeis.org

0, 5, 10, 20, 21, 40, 42, 80, 84, 85, 160, 168, 170, 320, 336, 340, 341, 640, 645, 672, 680, 682, 1280, 1285, 1290, 1344, 1360, 1364, 1365, 2560, 2565, 2570, 2580, 2581, 2688, 2693, 2720, 2728, 2730, 5120, 5125, 5130, 5140, 5141, 5160, 5162, 5376

Offset: 0

Antti Karttunen, Jan 30 2006

nonn

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

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

Cf. A048717, A115767, A115770. Subset of A115772 ? A115776 gives the terms of A115772 which do not occur here. Differs from A062052 for the first time at n=18, where A115774(18)=645 while A062052(18)=672. A115775 shows this sequence in binary.

A048733 a(n) = A048730(n)/4.

Original entry on oeis.org

0, 0, 0, 3, 0, 2, 6, 7, 0, 0, 4, 7, 12, 14, 14, 15, 0, 0, 0, 3, 8, 10, 14, 15, 24, 24, 28, 31, 28, 30, 30, 31, 0, 0, 0, 3, 0, 2, 6, 7, 16, 16, 20, 23, 28, 30, 30, 31, 48, 48, 48, 51, 56, 58, 62, 63, 56, 56, 60, 63, 60, 62, 62, 63, 0, 0, 0, 3, 0, 2, 6, 7, 0, 0, 4, 7, 12, 14, 14, 15, 32, 32

Offset: 0

Antti Karttunen

A048715 gives all n for which a(n) = 0, A048717 gives all n for which a(n) = n.

Paolo Xausa, Table of n, a(n) for n = 0..8191
Michael De Vlieger, Log log scatterplot of a(n), n = 0..2^20.

Cf. A048715, A048717, A048730.

A048733[n_] := (7*n - BitXor[n, 2*n, 4*n])/4;
Array[A048733, 100, 0] (* Paolo Xausa, Aug 06 2025 *)

a(n)=(7*n - bitxor(n, bitxor(2*n, 4*n)))/4 \\ Charles R Greathouse IV, Oct 03 2016

a(n) = ((n*7)-Xmult(n, 7))/4.

A115770 Integers i such that 7*i = A048720bi(11, i), where A048720bi implements the dyadic function given in A048720 (see A001317).

Original entry on oeis.org

0, 7, 14, 15, 28, 30, 31, 56, 60, 62, 63, 112, 120, 124, 126, 127, 224, 240, 248, 252, 254, 255, 448, 455, 480, 496, 504, 508, 510, 511, 896, 903, 910, 911, 960, 967, 992, 1008, 1016, 1020, 1022, 1023, 1792, 1799, 1806, 1807, 1820, 1822, 1823, 1920

Offset: 0

Antti Karttunen, Jan 30 2006

nonn

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

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

Row 7 of A115872 (conjecture: also row 5).
Cf. A001317, A048717, A048720, A115767, A115772, A115774, A115776.
A115771 shows this sequence in binary.

A284555 Positions of zeros in A284557.

Original entry on oeis.org

0, 3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 24, 28, 30, 31, 33, 36, 40, 45, 48, 51, 56, 60, 62, 63, 66, 72, 77, 80, 83, 89, 90, 96, 99, 101, 102, 103, 107, 112, 115, 120, 124, 126, 127, 129, 132, 139, 144, 147, 153, 154, 160, 163, 165, 166, 167, 171, 178, 180, 187, 189, 192, 195, 197, 198, 199, 201, 202, 204, 206, 207

Offset: 0

Antti Karttunen, Apr 10 2017

Indexing starts from zero, because a(0) = 0 is a special case in this list.

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

Cf. A284557, A048727.

Cf. A048717 (a subsequence).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A048715 Binary expansion matches (100(0)*)*(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Python

Formula

Extensions

A048719 Binary expansion matches ((0)*0011)*(0*).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A115772 Integers i such that 13*i = A048720bi(21,i).

Views

Author

Keywords

Comments

Links

Crossrefs

A115774 Integers i such that 15*i = A048720bi(23,i).

Views

Author

Keywords

Comments

Links

Crossrefs

A048733 a(n) = A048730(n)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A115770 Integers i such that 7*i = A048720bi(11, i), where A048720bi implements the dyadic function given in A048720 (see A001317).

Views

Author

Keywords

Comments

Links

Crossrefs

A284555 Positions of zeros in A284557.

Views

Author

Keywords

Comments

Links

Crossrefs

A048715 Binary expansion matches (100(0))(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

A048719 Binary expansion matches ((0)0011)(0*).