A115857 If n is a power of 2, then a(n) = n, otherwise a(n) is the smallest integer m > n, for which there exists an odd number i <= n^3 such that n*i = A048720(m, i), where A048720 is carryless base-2 multiplication.

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, 78, 75, 200, 89, 122, 91, 92, 93, 126

Offset

1,2

Comments

The original name was "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.", but that might not be well defined when the range of i has not been constrained. See A391571, A391573 and arrays A391925, A391926 for variants of this same theme. - Antti Karttunen, Dec 15 2025

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

Links

Antti Karttunen, Table of n, a(n) for n = 1..207

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

Index entries for sequences related to binary expansion of n.

Index entries for sequences related to carryless arithmetic.

Formula

For all n >= 1, a(2*n) = 2*a(n).

For all n >= 1, n * A391567(n) = A048720(a(n), A391567(n)). - Antti Karttunen, Dec 16 2025

Example

For n = 19, a(19) = 23 and A391567(19) = 3, and we have A048720(3,23) = 57 = 19*3. - Antti Karttunen, Dec 16 2025

Prog

(PARI)
A048720(b, c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A065621(n) = bitxor(n-1, n+n-1);
A209229(n) = (n && !bitand(n, n-1));
A115857(n) = if(A209229(n), n, for(m=n+1, A065621(n), forstep(i=1, n^3, 2, if((n*i)==A048720(m, i), return(m)))); (0)); \\ Antti Karttunen, Dec 15 2025

Crossrefs

Cf. A115858 (bisection, the odd terms).

Differs from A065621 for the first time at n=19, where a(19)=23, while A065621(19)=55. The positions of differences is given by A391568.

Cf. A115859, A115861, A115869, A115871, A115872, A115873.

Cf. A391567 (gives the corresponding number i), A391571, A391573 (variants).

Cf. also A391925, A391926.

Sequence in context: A388943 A329064 A102514 * A065621 A036565 A054787

Adjacent sequences: A115854 A115855 A115856 * A115858 A115859 A115860

Keyword

nonn,base

Author

Antti Karttunen, Feb 07 2006

Extensions

Definition revised and more terms added by Antti Karttunen, Dec 16 2025

Status

approved