cp's OEIS Frontend

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

%I A234742 #60 Apr 15 2023 15:34:08
%S A234742 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,
%T A234742 26,63,28,33,54,31,32,93,162,91,84,37,38,99,72,41,98,75,44,189,78,47,
%U A234742 48,77,50,243,52,57,126,55,56,117,66,59,108,61,62,147,64,441
%N A234742 Product of the binary encodings of the irreducible factors (with multiplicity) of the polynomial over GF(2) whose encoding is n.
%C A234742 "Product" refers to the ordinary multiplication of integers.
%C A234742 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.
%C A234742 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.]
%C A234742 Specifically, for all n, a(A091209(n)) > A091209(n).
%C A234742 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.
%C A234742 Starting with various terms (primes) in A235033 and iterating the map A234742, we get 5 -> 9 -> 21 -> 49 -> 77 -> 177 -> 333 = a(333).
%C A234742 Another example: 17 -> 81 -> 169 -> 309 -> 721 = a(721).
%C A234742 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.)
%C A234742 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
%C A234742 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.
%H A234742 Antti Karttunen, <a href="/A234742/b234742.txt">Table of n, a(n) for n = 0..8192</a>
%H A234742 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A234742 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.
%F A234742 a(2n) = 2*a(n).
%F A234742 a(A235035(n)) = A235035(n).
%F A234742 A236379(n) = a(n) - n.
%F A234742 For all n, a(n) >= A236837(n).
%e A234742 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.
%e A234742 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.
%e A234742 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.
%e A234742 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.
%o A234742 (Scheme, with _Antti Karttunen_'s IntSeq-library)
%o A234742 (definec (A234742 n) (if (zero? n) n (reduce * 1 (GF2Xfactor n))))
%o A234742 (PARI) 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
%Y A234742 A235035 gives the k for which a(k)=k.
%Y A234742 A236853(n) gives the number of times n occurs in this sequence.
%Y A234742 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).
%Y A234742 Cf. A014580, A048720, A234741, A236379, A236837, A236851 & A236852, A115857, A115872.
%Y A234742 Cf. also A260712, A260713, A260716 and A244323, A260729, A260735, A260441 (iterations starting from various terms of A236844).
%K A234742 nonn,base
%O A234742 0,3
%A A234742 _Antti Karttunen_, Jan 22 2014