Displaying 1-10 of 23 results found.
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
FORMULA
a(2^k) = 1, a(2n) = a(n).
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, 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];
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
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];
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];
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.
+10
154
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
COMMENTS
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
LINKS
N. J. A. Sloane, Transforms: Maple implementation of binary eXclusive OR (XORnos).
FORMULA
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
EXAMPLE
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 ...
...
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)
MAPLE
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;
MATHEMATICA
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];
PROG
(PARI)
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);
CROSSREFS
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. See A014580 for further sequences related to the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the integer encoding. Associated additive operation: A003987. See A091202 (and its variants) and A278233 for maps from/to ordinary multiplication.
Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.
+10
58
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
COMMENTS
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
REFERENCES
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)
FORMULA
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) = 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
EXAMPLE
a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.
PROG
(PARI) 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))
(Haskell)
import Data.Bits (xor, (.&.))
a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
(Python)
(Python)
Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.
+10
39
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
COMMENTS
"Product" refers to the ordinary multiplication of integers.
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.] 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.
FORMULA
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).
EXAMPLE
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.
PROG
(definec ( A234742 n) (if (zero? n) n (reduce * 1 (GF2Xfactor n))))
CROSSREFS
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).
Factorization-preserving bijection from nonnegative integers to GF(2)[X]-polynomials, version which fixes the elements that are irreducible in both semirings.
+10
14
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
COMMENTS
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.
FORMULA
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.
EXAMPLE
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.
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.
+10
10
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
EXAMPLE
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
PROG
(Scheme)
(define (A277320bi row col) (A048720bi ( A065621 row) col))
CROSSREFS
Cf. A277820 (array obtained by selecting only the columns with an index A001317(k), k=0..).
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.
+10
9
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
COMMENTS
Here * stands for ordinary multiplication and X means carryless (GF(2)[X]) multiplication ( A048720).
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.
+10
9
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
PROG
(PARI)
A048720(b, c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
Binary expansion matches ((0)*00(1*)11)*(0*).
+10
8
0, 3, 6, 7, 12, 14, 15, 24, 28, 30, 31, 48, 51, 56, 60, 62, 63, 96, 99, 102, 103, 112, 115, 120, 124, 126, 127, 192, 195, 198, 199, 204, 206, 207, 224, 227, 230, 231, 240, 243, 248, 252, 254, 255, 384, 387, 390, 391
COMMENTS
In binary expansion, 1-bits occur only in groups of two or more, separated from other such groups by at least two 0-bits.
Integers that satisfy A048727(n) = 3*n.
MATHEMATICA
filterQ[n_] := !MatchQ[IntegerDigits[n, 2], {1}|{1, 0, ___}|{___, 0, 1}|{___, 1, 0, 1, ___}|{___, 0, 1, 0, ___}];
Search completed in 0.019 seconds
|