A277333 -id:A277333 - cp's OEIS frontend

A277317 Numbers k such that A277333(k) is a prime.

3, 6, 18, 30, 270, 450, 630, 2310, 6750, 9450, 22050, 510510, 727650, 2668050, 3543750, 4961250, 25467750, 29099070

Offset: 1

Antti Karttunen, Oct 10 2016

Sequence A277316 sorted into ascending order. See comments in that entry.

Terms k present in A277319 for which A260443(A048675(k)) = k. - David A. Corneth and Antti Karttunen, Oct 13 2016

Cf. A277316.
Cf. A000040, A010051, A048675, A260443, A277333.
Intersection of A260442 and A277319.
Also, after the initial term, the intersection of A277200 and A277319.

\\ Naive program that does not work very far:
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From Michel Marcus
A048675(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; \\ Michel Marcus, Oct 10 2016
A260443(n) = if(n<2, n+1, if(!(n%2), A003961(A260443(n/2)), A260443((n-1)/2) * A260443((n+1)/2)));
A277333(n) = { my(k=A048675(n)); if(A260443(k) == n, k, 0); } ;
isA277317 = n -> isprime(A277333(n));  \\ Naive version, very slow.
A061395(n) =  if(1==n, 0, primepi(vecmax(factor(n)[, 1]))); \\ After M. F. Hasler's code for A006530.
isA277317(n) = { my(k); if(3==n, 1, if(n%2 || (omega(n) < A061395(n)), 0, k = A048675(n); if((A260443(k) == n), isprime(k), 0))); }; \\ Somewhat optimized.
i=0; n=0; while(i < 30, n++; if(isA277317(n), i++; write("b277317.txt", i, " ", n)));

;; With Antti Karttunen's IntSeq-library)
(define A277317 (MATCHING-POS 1 1 (lambda (n) (= 1 (A010051 (A277333 n))))))

;; With Antti Karttunen's IntSeq-library)
;; Doing search in another order:
(define A277317 (COMPOSE A277319 (MATCHING-POS 1 1 (lambda (n) (= (A260443 (A048675 (A277319 n))) (A277319 n))))))

A277417 Numbers n for which A248663(n) = A277333(n).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 16, 17, 19, 23, 25, 29, 30, 31, 35, 36, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 77, 79, 81, 83, 89, 97, 100, 101, 103, 105, 107, 109, 113, 121, 127, 131, 137, 139, 143, 144, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 196, 197, 199, 210, 211, 221, 223, 225, 227, 229, 233

Offset: 1

Antti Karttunen, Oct 27 2016

nonn

After its initial 1-term, A073485 gives those n for which A248663(n) = A277333(n) > 0.

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

Union of A000290 (apart from its initial zero) and A073485.
Cf. A248663, A277333.
Cf. also A260443.

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

			From _Gus Wiseman_, May 22 2024: (Start)
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
   30: {1,2,3}
   40: {1,1,1,3}
   54: {1,2,2,2}
   72: {1,1,1,2,2}
   96: {1,1,1,1,1,2}
  128: {1,1,1,1,1,1,1}
(End)

Antti Karttunen, Table of n, a(n) for n = 1..1024
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]

Row 2 of A104244.
Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
The formula section details how the sequence maps the terms of A329050, A329332.
A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
Numbers k such that a(k) is prime are A277319, counts A372688.
Grouping by image gives A277905.
A014499 lists binary indices of prime numbers.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
Binary indices:
- listed A048793, sum A029931
- reversed A272020
- opposite A371572, sum A230877
- length A000120, complement A023416
- min A001511, opposite A000012
- max A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
Cf. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
Cf. A087207, A097248.

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
map(f, [$1..100]); # Robert Israel, Oct 10 2016

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)

a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ Michel Marcus, Oct 10 2016

\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020

from sympy import factorint, primepi
def a(n):
    if n==1: return 0
    f=factorint(n)
    return sum([f[i]*2**(primepi(i) - 1) for i in f])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 19 2017

a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
From Antti Karttunen, Jul 29 2015: (Start)
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
Other identities. For all n >= 0:
a(A019565(n)) = n.
a(A260443(n)) = n.
a(A206296(n)) = A000129(n).
a(A005940(n+1)) = A087808(n).
a(A007913(n)) = A248663(n).
a(A007947(n)) = A087207(n).
a(A283477(n)) = A005187(n).
a(A284003(n)) = A006068(n).
a(A285101(n)) = A028362(1+n).
a(A285102(n)) = A068052(n).
Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016
From Peter Munn, Jan 31 2020: (Start)
a(n^2) = a(A003961(n)) = 2 * a(n).
a(A297845(n,k)) = a(n) * a(k).
a(n) = a(A225546(n)).
a(A329332(n,k)) = n * k.
a(A329050(n,k)) = 2^(n+k).
(End)
From Antti Karttunen, Feb 02-25 2020, Feb 01 2021: (Start)
a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
a(n) = a(A097248(n)).
For n >= 2:
A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
For n >= 1, A331750(n) = a(A000203(n)).
For n >= 1, the following chains hold:
A293447(n) >= a(n) >= A331740(n) >= A331591(n).
a(n) >= A087207(n) >= A248663(n).
(End)
a(n) = A087207(A097248(n)). - Flávio V. Fernandes, Jul 16 2025

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

A260443 Prime factorization representation of Stern polynomials: a(0) = 1, a(1) = 2, a(2n) = A003961(a(n)), a(2n+1) = a(n)*a(n+1).

Original entry on oeis.org

1, 2, 3, 6, 5, 18, 15, 30, 7, 90, 75, 270, 35, 450, 105, 210, 11, 630, 525, 6750, 245, 20250, 2625, 9450, 77, 15750, 3675, 47250, 385, 22050, 1155, 2310, 13, 6930, 5775, 330750, 2695, 3543750, 128625, 1653750, 847, 4961250, 643125, 53156250, 18865, 24806250, 202125, 727650, 143, 1212750, 282975, 57881250, 29645, 173643750, 1414875, 18191250, 1001

Offset: 0

Antti Karttunen, Jul 28 2015

The exponents in the prime factorization of term a(n) give the coefficients of the n-th Stern polynomial. See A125184 and the examples.
None of the terms have prime gaps in their factorization, i.e., all can be found in A073491.
Contains neither perfect squares nor prime powers with exponent > 1. A277701 gives the positions of the terms that are 2*square. - Antti Karttunen, Oct 27 2016
Many of the derived sequences (like A002487) have similar "Fir forest" or "Gaudian cathedrals" style scatter plot. - Antti Karttunen, Mar 21 2017

			n    a(n)   prime factorization    Stern polynomial
------------------------------------------------------------
0       1   (empty)                B_0(x) = 0
1       2   p_1                    B_1(x) = 1
2       3   p_2                    B_2(x) = x
3       6   p_2 * p_1              B_3(x) = x + 1
4       5   p_3                    B_4(x) = x^2
5      18   p_2^2 * p_1            B_5(x) = 2x + 1
6      15   p_3 * p_2              B_6(x) = x^2 + x
7      30   p_3 * p_2 * p_1        B_7(x) = x^2 + x + 1
8       7   p_4                    B_8(x) = x^3
9      90   p_3 * p_2^2 * p_1      B_9(x) = x^2 + 2x + 1

Alois P. Heinz, Table of n, a(n) for n = 0..4096 (first 1025 terms from Antti Karttunen)

Same sequence sorted into ascending order: A260442.
Cf. A000040, A000079, A000225, A001222, A002487, A003415, A003961, A005811, A007949, A046523, A056239, A073491, A090880, A097249, A101979, A125184, A178590, A186891, A206284, A277314, A277315, A277325, A277326, A277329, A277330, A277701, A277705, A277899, A278243, A278530, A278544, A284010, A284011.
Cf. also A048675, A277333 (left inverses).
Cf. A277323, A277324 (bisections), A277200 (even terms sorted), A277197 (first differences), A277198.
Cf. A277316 (values at primes), A277318.
Cf. A023758 (positions of squarefree terms), A101082 (of terms not squarefree), A277702 (positions of records), A277703 (their values).
Cf. A283992, A283993 (number of irreducible, reducible polynomials in range 1 .. n).
Cf. also A206296 (Fibonacci polynomials similarly represented).

b:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
a:= proc(n) option remember; `if`(n<2, n+1,
      `if`(irem(n, 2, 'h')=0, b(a(h)), a(h)*a(n-h)))
    end:
seq(a(n), n=0..56);  # Alois P. Heinz, Jul 04 2024

a[n_] := a[n] = Which[n < 2, n + 1, EvenQ@ n, Times @@ Map[#1^#2 & @@ # &, FactorInteger[#] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[# == 1] &@ a[n/2], True, a[#] a[# + 1] &[(n - 1)/2]]; Table[a@ n, {n, 0, 56}] (* Michael De Vlieger, Apr 05 2017 *)

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From Michel Marcus
A260443(n) = if(n<2, n+1, if(n%2, A260443(n\2)*A260443(n\2+1), A003961(A260443(n\2)))); \\ After Charles R Greathouse IV's code for "ps" in A186891.
\\ Antti Karttunen, Oct 11 2016

from sympy import factorint, prime, primepi
from functools import reduce
from operator import mul
def a003961(n):
    F = factorint(n)
    return 1 if n==1 else reduce(mul, (prime(primepi(i) + 1)**F[i] for i in F))
def a(n): return n + 1 if n<2 else a003961(a(n//2)) if n%2==0 else a((n - 1)//2)*a((n + 1)//2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 21 2017

;; Uses memoization-macro definec:
(definec (A260443 n) (cond ((<= n 1) (+ 1 n)) ((even? n) (A003961 (A260443 (/ n 2)))) (else (* (A260443 (/ (- n 1) 2)) (A260443 (/ (+ n 1) 2))))))
;; A more standalone version added Oct 10 2016, requiring only an implementation of A000040 and the memoization-macro definec:
(define (A260443 n) (product_primes_to_kth_powers (A260443as_coeff_list n)))
(define (product_primes_to_kth_powers nums) (let loop ((p 1) (nums nums) (i 1)) (cond ((null? nums) p) (else (loop (* p (expt (A000040 i) (car nums))) (cdr nums) (+ 1 i))))))
(definec (A260443as_coeff_list n) (cond ((zero? n) (list)) ((= 1 n) (list 1)) ((even? n) (cons 0 (A260443as_coeff_list (/ n 2)))) (else (add_two_lists (A260443as_coeff_list (/ (- n 1) 2)) (A260443as_coeff_list (/ (+ n 1) 2))))))
(define (add_two_lists nums1 nums2) (let ((len1 (length nums1)) (len2 (length nums2))) (cond ((< len1 len2) (add_two_lists nums2 nums1)) (else (map + nums1 (append nums2 (make-list (- len1 len2) 0)))))))

a(0) = 1, a(1) = 2, a(2n) = A003961(a(n)), a(2n+1) = a(n)*a(n+1).
Other identities. For all n >= 0:
A001221(a(n)) = A277314(n). [#nonzero coefficients in each polynomial.]
A001222(a(n)) = A002487(n). [When each polynomial is evaluated at x=1.]
A048675(a(n)) = n.          [at x=2.]
A090880(a(n)) = A178590(n). [at x=3.]
A248663(a(n)) = A264977(n). [at x=2 over the field GF(2).]
A276075(a(n)) = A276081(n). ["at factorials".]
A156552(a(n)) = A277020(n). [Converted to "unary-binary" encoding.]
A051903(a(n)) = A277315(n). [Maximal coefficient.]
A277322(a(n)) = A277013(n). [Number of irreducible polynomial factors.]
A005361(a(n)) = A277325(n). [Product of nonzero coefficients.]
A072411(a(n)) = A277326(n). [And their LCM.]
A007913(a(n)) = A277330(n). [The squarefree part.]
A000005(a(n)) = A277705(n). [Number of divisors.]
A046523(a(n)) = A278243(n). [Filter-sequence.]
A284010(a(n)) = A284011(n). [True for n > 1. Another filter-sequence.]
A003415(a(n)) = A278544(n). [Arithmetic derivative.]
A056239(a(n)) = A278530(n). [Weighted sum of coefficients.]
A097249(a(n)) = A277899(n).
a(A000079(n)) = A000040(n+1).
a(A000225(n)) = A002110(n).
a(A000051(n)) = 3*A002110(n).
For n >= 1, a(A000918(n)) = A070826(n).
A007949(a(n)) is the interleaving of A000035 and A005811, probably A101979.
A061395(a(n)) = A277329(n).
Also, for all n >= 1:
A055396(a(n)) = A001511(n).
A252735(a(n)) = A061395(a(n)) - 1 = A057526(n).
a(A000040(n)) = A277316(n).
a(A186891(1+n)) = A277318(n). [Subsequence for irreducible polynomials].

More linking formulas added by Antti Karttunen, Mar 21 2017

A248663 Binary encoding of the prime factors of the squarefree part of n.

Original entry on oeis.org

0, 1, 2, 0, 4, 3, 8, 1, 0, 5, 16, 2, 32, 9, 6, 0, 64, 1, 128, 4, 10, 17, 256, 3, 0, 33, 2, 8, 512, 7, 1024, 1, 18, 65, 12, 0, 2048, 129, 34, 5, 4096, 11, 8192, 16, 4, 257, 16384, 2, 0, 1, 66, 32, 32768, 3, 20, 9, 130, 513, 65536, 6, 131072, 1025, 8, 0, 36, 19

Offset: 1

Peter Kagey, Jan 11 2015

The binary digits of a(n) encode the prime factorization of A007913(n), where the i-th digit from the right is 1 if and only if prime(i) divides A007913(n), otherwise 0. - Robert Israel, Jan 12 2015
Old name: a(1) = 0; a(A000040(n)) = 2^(n-1), and a(n*m) = a(n) XOR a(m).
XOR is the bitwise exclusive or operation (A003987).
a(k^2) = 0 for a natural number k.
Equivalently, the i-th binary digit from the right is 1 iff prime(i) divides n an odd number of times, otherwise zero. - Ethan Beihl, Oct 15 2016
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443, with scheme explained in A206284), then A048675(n) gives the evaluation of that polynomial at x=2. This sequence is otherwise similar, except the polynomial is evaluated over the field GF(2), which implies also that all its coefficients are essentially reduced modulo 2. - Antti Karttunen, Dec 11 2015
Squarefree numbers (A005117) give the positions k where a(k) = A048675(k). - Antti Karttunen, Oct 29 2016
From Peter Munn, Jun 07 2021: (Start)
When we encode polynomials with nonnegative integer coefficients as described by Antti Karttunen above, polynomial addition is represented by integer multiplication, multiplication is represented by A297845(.,.), and this sequence represents a surjective semiring homomorphism to polynomials in GF(2)[x] (encoded as described in A048720). The mapping of addition operations by this homomorphism is part of the sequence definition: "a(n*m) = a(n) XOR a(m)". The mapping of multiplication is given by a(A297845(n, k)) = A048720(a(n), a(k)).
In a related way, A329329 defines a representation of a different set of polynomials as positive integers, namely polynomials in GF(2)[x,y].
Let P_n(x,y) denote the polynomial represented, as in A329329, by n >= 1. If 0 is substituted for y in P_n(x,y), we get a polynomial P'_n(x,y) (in which y does not appear, of course) that is equivalent to a polynomial P'_n(x) in GF(2)[x]. a(n) is the integer encoding of P'_n(x) (described in A048720).
Viewed as above, this sequence represents another surjective homomorphism, a homomorphism between polynomial rings, with A329329(.,.)/A059897(.,.) and A048720(.,.)/A003987(.,.) as the respective ring operations.
a(n) can be composed as a(n) = A048675(A007913(n)) and the effect of the A007913(.) component corresponds to different operations on the respective polynomial domains of the two homomorphisms described above. In the first homomorphism, coefficients are reduced modulo 2; in the second, 0 is substituted for y. This is illustrated in the examples.
(End)

			a(3500) = a(2^2 * 5^3 * 7) = a(2) XOR a(2) XOR a(5) XOR a(5) XOR a(5) XOR a(7) = 1 XOR 1 XOR 4 XOR 4 XOR 4 XOR 8 = 0b0100 XOR 0b1000 = 0b1100 = 12.
From _Peter Munn_, Jun 07 2021: (Start)
The examples in the table below illustrate the homomorphisms (between polynomial structures) represented by this sequence.
The staggering of the rows is to show how the mapping n -> A007913(n) -> A048675(A007913(n)) = a(n) relates to the encoded polynomials, as not all encodings are relevant at each stage.
For an explanation of each polynomial encoding, see the sequence referenced in the relevant column heading. (Note also that A007913 generates squarefree numbers, and with these encodings, all squarefree numbers represent equivalent polynomials in N[x] and GF(2)[x,y].)
                     |<-----    encoded polynomials    ----->|
  n  A007913(n) a(n) |         N[x]    GF(2)[x,y]    GF(2)[x]|
                     |Cf.:  A206284       A329329     A048720|
--------------------------------------------------------------
  24                            x+3         x+y+1
          6                     x+1           x+1
                  3                                       x+1
--------------------------------------------------------------
  36                           2x+2          xy+y
          1                       0             0
                  0                                         0
--------------------------------------------------------------
  60                        x^2+x+2       x^2+x+y
         15                   x^2+x         x^2+x
                  6                                     x^2+x
--------------------------------------------------------------
  90                       x^2+2x+1      x^2+xy+1
         10                   x^2+1         x^2+1
                  5                                     x^2+1
--------------------------------------------------------------
This sequence is a left inverse of A019565. A019565(.) maps a(n) to A007913(n) for all n, effectively reversing the second stage of the mapping from n to a(n) shown above. So, with the encodings used here, A019565(.) represents each of two injective homomorphisms that map polynomials in GF(2)[x] to equivalent polynomials in N[x] and GF(2)[x,y] respectively.
(End)

Peter Kagey, Table of n, a(n) for n = 1..5000
Eric Weisstein's World of Mathematics, Squarefree Part
Wikipedia, Polynomial ring
Index entries for sequences operating on GF(2)[X]-polynomials

Cf. A000040, A000079, A000720, A005117, A020639, A032742, A048672, A055396, A100112, A206284.
A048675 composed with A007913. A007814 composed with A225546.
A homomorphism from A297845/A003991 and from A329329/A059897 to A048720/A003987, mapping A206296 to A168081, A260443 to A264977, A265408 to A265407, A275734 to A275808, A276076 to A276074, A283477 to A006068.
A left inverse of A019565.
Other sequences used to express relationship between terms of this sequence: A003961, A007913, A331590, A334747.
Cf. also A099884, A277330.
A087207 is the analogous sequence with OR.
A277417 gives the positions where coincides with A277333.
A000290 gives the positions of zeros.

import Data.Bits (xor)
a248663 = foldr (xor) 0 . map (\i -> 2^(i - 1)) . a112798_row
-- Peter Kagey, Sep 16 2016

f:= proc(n)
local F,f;
F:= select(t -> t[2]::odd, ifactors(n)[2]);
add(2^(numtheory:-pi(f[1])-1), f = F)
end proc:
seq(f(i),i=1..100); # Robert Israel, Jan 12 2015

a[1] = 0; a[n_] := a[n] = If[PrimeQ@ n, 2^(PrimePi@ n - 1), BitXor[a[#], a[n/#]] &@ FactorInteger[n][[1, 1]]]; Array[a, 66] (* Michael De Vlieger, Sep 16 2016 *)

A248663(n) = vecsum(apply(p -> 2^(primepi(p)-1),factor(core(n))[,1])); \\ Antti Karttunen, Feb 15 2021

from sympy import factorint, primepi
from sympy.ntheory.factor_ import core
def a048675(n):
    f=factorint(n)
    return 0 if n==1 else sum([f[i]*2**(primepi(i) - 1) for i in f])
def a(n): return a048675(core(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 21 2017

require 'prime'
def f(n)
  a = 0
  reverse_primes = Prime.each(n).to_a.reverse
  reverse_primes.each do |prime|
    a <<= 1
    while n % prime == 0
      n /= prime
      a ^= 1
    end
  end
  a
end
(Scheme, with memoizing-macro definec)
(definec (A248663 n) (cond ((= 1 n) 0) ((= 1 (A010051 n)) (A000079 (- (A000720 n) 1))) (else (A003987bi (A248663 (A020639 n)) (A248663 (A032742 n)))))) ;; Where A003987bi computes bitwise-XOR as in A003987.
;; Alternatively:
(definec (A248663 n) (cond ((= 1 n) 0) (else (A003987bi (A000079 (- (A055396 n) 1)) (A248663 (A032742 n))))))
;; Antti Karttunen, Dec 11 2015

a(1) = 0; for n > 1, if n is a prime, a(n) = 2^(A000720(n)-1), otherwise a(A020639(n)) XOR a(A032742(n)). [After the definition.] - Antti Karttunen, Dec 11 2015
For n > 1, this simplifies to: a(n) = 2^(A055396(n)-1) XOR a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n. Cf. a similar formula for A048675.]
Other identities and observations. For all n >= 0:
a(n) = A048672(A100112(A007913(n))). - Peter Kagey, Dec 10 2015
From Antti Karttunen, Dec 11 2015, Sep 19 & Oct 27 2016, Feb 15 2021: (Start)
a(n) = a(A007913(n)). [The result depends only on the squarefree part of n.]
a(n) = A048675(A007913(n)).
a(A206296(n)) = A168081(n).
a(A260443(n)) = A264977(n).
a(A265408(n)) = A265407(n).
a(A275734(n)) = A275808(n).
a(A276076(n)) = A276074(n).
a(A283477(n)) = A006068(n).
(End)
From Peter Munn, Jan 09 2021 and Apr 20 2021: (Start)
a(n) = A007814(A225546(n)).
a(A019565(n)) = n; A019565(a(n)) = A007913(n).
a(A003961(n)) = 2 * a(n).
a(A297845(n, k)) = A048720(a(n), a(k)).
a(A329329(n, k)) = A048720(a(n), a(k)).
a(A059897(n, k)) = A003987(a(n), a(k)).
a(A331590(n, k)) = a(n) + a(k).
a(A334747(n)) = a(n) + 1.
(End)

New name from Peter Munn, Nov 01 2023

A260442 Sequence A260443 sorted into ascending order.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 11, 13, 15, 17, 18, 19, 23, 29, 30, 31, 35, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 75, 77, 79, 83, 89, 90, 97, 101, 103, 105, 107, 109, 113, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 210, 211, 221, 223, 227, 229, 233, 239, 241, 245, 251, 257, 263, 269, 270, 271, 277, 281, 283, 293, 307, 311

Offset: 0

Antti Karttunen, Jul 29 2015

nonn

Each term is a prime factorization encoding of one of the Stern polynomials. See A260443 for details.

Numbers n for which A260443(A048675(n)) = n. - Antti Karttunen, Oct 14 2016

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A003961, A048675, A260443.
Subsequence of A073491.
From 2 onward the positions of nonzeros in A277333.
Various subsequences: A000040, A002110, A070826, A277317, A277200 (even terms).  Also all terms of A277318 are included here.
Cf. also A277323, A277324 and permutation pair A277415 & A277416.

allocatemem(2^30);
A048675(n) = my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; \\ Michel Marcus, Oct 10 2016
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From Michel Marcus
A260443(n) = if(n<2, n+1, if(n%2, A260443(n\2)*A260443(n\2+1), A003961(A260443(n\2))));
isA260442(n) = (A260443(A048675(n)) == n);  \\ The most naive version.
A055396(n) = if(n==1, 0, primepi(factor(n)[1, 1])) \\ Charles R Greathouse IV, Apr 23 2015
A061395(n) =  if(1==n, 0, primepi(vecmax(factor(n)[, 1]))); \\ After M. F. Hasler's code for A006530.
isA260442(n) = ((1==n) || isprime(n) || ((omega(n) == 1+(A061395(n)-A055396(n))) && (A260443(A048675(n)) == n))); \\ Somewhat optimized.
i=0; n=0; while(i < 10001, n++; if(isA260442(n), write("b260442.txt", i, " ", n); i++));
\\ Antti Karttunen, Oct 14 2016

from sympy import factorint, prime, primepi
from operator import mul
from functools import reduce
def a048675(n):
    F=factorint(n)
    return 0 if n==1 else sum([F[i]*2**(primepi(i) - 1) for i in F])
def a003961(n):
    F=factorint(n)
    return 1 if n==1 else reduce(mul, [prime(primepi(i) + 1)**F[i] for i in F])
def a(n): return n + 1 if n<2 else a003961(a(n//2)) if n%2==0 else a((n - 1)//2)*a((n + 1)//2)
print([n for n in range(301) if a(a048675(n))==n]) # Indranil Ghosh, Jun 21 2017

;; With Antti Karttunen's IntSeq-library.
(define A260442 (FIXED-POINTS 0 1 (COMPOSE A260443 A048675)))
;; An optimized version:
(define A260442 (MATCHING-POS 0 1 (lambda (n) (or (= 1 n) (= 1 (A010051 n)) (and (not (< (A001221 n) (+ 1 (A243055 n)))) (= n (A260443 (A048675 n))))))))
;; Antti Karttunen, Oct 14 2016

cp's OEIS Frontend

A277317 Numbers k such that A277333(k) is a prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Scheme

Scheme

A277417 Numbers n for which A248663(n) = A277333(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A260443 Prime factorization representation of Stern polynomials: a(0) = 1, a(1) = 2, a(2n) = A003961(a(n)), a(2n+1) = a(n)*a(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Scheme

Formula

Extensions

A248663 Binary encoding of the prime factors of the squarefree part of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Ruby

Formula

Extensions

A260442 Sequence A260443 sorted into ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Scheme