cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-9 of 9 results.

A305417 Permutation of natural numbers: a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).

Original entry on oeis.org

1, 2, 3, 4, 7, 6, 5, 8, 11, 14, 9, 12, 21, 10, 15, 16, 13, 22, 29, 28, 49, 18, 27, 24, 69, 42, 63, 20, 107, 30, 17, 32, 19, 26, 23, 44, 35, 58, 39, 56, 127, 98, 83, 36, 151, 54, 45, 48, 81, 138, 207, 84, 475, 126, 65, 40, 743, 214, 189, 60, 273, 34, 51, 64, 25, 38, 53, 52, 121, 46, 57, 88, 173, 70, 101, 116, 233, 78, 105, 112, 199, 254, 129
Offset: 0

Views

Author

Antti Karttunen, Jun 10 2018

Keywords

Comments

This is GF(2)[X] analog of A005940, but note the indexing: here the domain starts from 0, although the range excludes zero.
This sequence can be represented as a binary tree. Each child to the left is obtained by applying A305421 to the parent, and each child to the right is obtained by doubling the parent:
1
|
...................2...................
3 4
7......../ \........6 5......../ \........8
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
11 14 9 12 21 10 15 16
13 22 29 28 49 18 27 24 69 42 63 20 107 30 17 32
Sequence A305427 is obtained by scanning the same tree level by level from right to left.

Crossrefs

Cf. A305418 (inverse), A305427 (mirror image).
Cf. A014580 (left edge from 2 onward), A305421.
Cf. also A005940, A052330, A091202.

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
    A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
    A305417(n) = if(0==n,(1+n),if(!(n%2),A305421(A305417(n/2)),2*(A305417((n-1)/2))));

Formula

a(0) = 1, a(2n) = A305421(a(n)), a(2n+1) = 2*a(n).
a(n) = A305427(A054429(n)).
For all n >= 1, a(A000079(n-1)) = A014580(n).

A305427 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 6, 7, 16, 15, 10, 21, 12, 9, 14, 11, 32, 17, 30, 107, 20, 63, 42, 69, 24, 27, 18, 49, 28, 29, 22, 13, 64, 51, 34, 273, 60, 189, 214, 743, 40, 65, 126, 475, 84, 207, 138, 81, 48, 45, 54, 151, 36, 83, 98, 127, 56, 39, 58, 35, 44, 23, 26, 19, 128, 85, 102, 1911, 68, 819, 546, 4113, 120, 455, 378, 3253, 428, 1833, 1486, 925, 80
Offset: 0

Views

Author

Antti Karttunen, Jun 10 2018

Keywords

Comments

Note the indexing: Domain starts from 0, while range starts from 1.
This is GF(2)[X] analog of A163511.
This sequence can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A305421 to the parent:
1
|
...................2...................
4 3
8......../ \........5 6......../ \........7
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
16 15 10 21 12 9 14 11
32 17 30 107 20 63 42 69 24 27 18 49 28 29 22 13
etc.
Sequence A305417 is obtained by scanning the same tree level by level from right to left.

Crossrefs

Cf. A305428 (inverse), A305417 (mirror image).
Cf. A305421.
Cf. also A091202, A163511.

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
    A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
    A305427(n) = if(n<=1,(1+n),if(!(n%2),2*A305427(n/2),A305421(A305427((n-1)/2))));

Formula

a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A305421(a(n)).
a(n) = A305417(A054429(n)).

A305423 Permutation of natural numbers: a(n) = (A305421(n)+1)/2.

Original entry on oeis.org

1, 2, 4, 3, 11, 5, 6, 8, 25, 32, 7, 14, 10, 15, 54, 9, 137, 42, 13, 33, 35, 12, 61, 23, 16, 27, 76, 20, 18, 95, 19, 26, 126, 410, 87, 123, 21, 22, 117, 98, 24, 104, 47, 29, 499, 70, 28, 60, 64, 17, 956, 48, 40, 221, 30, 53, 184, 51, 31, 228, 34, 56, 238, 43, 641, 135, 37, 683, 41, 252, 229, 144, 44, 62, 775, 63, 90, 158, 109, 163, 131, 57
Offset: 1

Views

Author

Antti Karttunen, Jun 08 2018

Keywords

Crossrefs

Cf. A305424 (inverse).
Cf. also A048673.

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
    A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
    A305423(n) = ((1+A305421(n))/2);

Formula

a(n) = (A305421(n)+1)/2.

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

Original entry on oeis.org

1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23, 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, 37, 243, 65, 57, 77, 225, 41, 69, 85, 189, 43, 165, 47, 117, 175, 87, 53, 405, 121, 147, 95, 153, 59, 375, 91, 297, 115, 93, 61, 315, 67, 111, 275, 729, 119
Offset: 1

Views

Author

Keywords

Comments

Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021
Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021
a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001
a(n) and n have the same number of distinct primes with (A001222) and without multiplicity (A001221). - Michel Marcus, Jun 13 2014
From Antti Karttunen, Nov 01 2019: (Start)
More generally, a(n) has the same prime signature as n, A046523(a(n)) = A046523(n). Also A246277(a(n)) = A246277(n) and A287170(a(n)) = A287170(n).
Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.
(End)

Examples

			a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
a(A002110(n)) = A002110(n + 1) / 2.
		

References

  • Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).

Crossrefs

See A045965 for another version.
Row 1 of table A242378 (which gives the "k-th powers" of this sequence), row 3 of A297845 and of A306697. See also arrays A066117, A246278, A255483, A308503, A329050.
Cf. A064989 (a left inverse), A064216, A000040, A002110, A000265, A027746, A046523, A048673 (= (a(n)+1)/2), A108228 (= (a(n)-1)/2), A191002 (= a(n)*n), A252748 (= a(n)-2n), A286385 (= a(n)-sigma(n)), A283980 (= a(n)*A006519(n)), A341529 (= a(n)*sigma(n)), A326042, A049084, A001221, A001222, A122111, A225546, A260443, A245606, A244319, A246269 (= A065338(a(n))), A322361 (= gcd(n, a(n))), A305293.
Cf. A249734, A249735 (bisections).
Cf. A246261 (a(n) is of the form 4k+1), A246263 (of the form 4k+3), A246271, A246272, A246259, A246281 (n such that a(n) < 2n), A246282 (n such that a(n) > 2n), A252742.
Cf. A275717 (a(n) > a(n-1)), A275718 (a(n) < a(n-1)).
Cf. A003972 (Möbius transform), A003973 (Inverse Möbius transform), A318321.
Cf. A300841, A305421, A322991, A250469, A269379 for analogous shift-operators in other factorization and quasi-factorization systems.
Cf. also following permutations and other sequences that can be defined with the help of this sequence: A005940, A163511, A122111, A260443, A206296, A265408, A265750, A275733, A275735, A297845, A091202 & A091203, A250245 & A250246, A302023 & A302024, A302025 & A302026.
A version for partition numbers is A003964, strict A357853.
A permutation of A005408.
Applying the same transformation again gives A357852.
Other multiplicative sequences: A064988, A357977, A357978, A357980, A357983.
A056239 adds up prime indices, row-sums of A112798.

Programs

  • Haskell
    a003961 1 = 1
    a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
    -- Reinhard Zumkeller, Apr 09 2012, Oct 09 2011
    (MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
    (require 'factor)
    (define (A003961 n) (apply * (map A000040 (map 1+ (map A049084 (factor n))))))
    ;; Antti Karttunen, May 20 2014
    
  • Maple
    a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
    seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017
  • Mathematica
    a[p_?PrimeQ] := a[p] = Prime[ PrimePi[p] + 1]; a[1] = 1; a[n_] := a[n] = Times @@ (a[#1]^#2& @@@ FactorInteger[n]); Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Dec 01 2011, updated Sep 20 2019 *)
    Table[Times @@ Map[#1^#2 & @@ # &, FactorInteger[n] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[n == 1], {n, 65}] (* Michael De Vlieger, Mar 24 2017 *)
  • PARI
    a(n)=local(f); if(n<1,0,f=factor(n); prod(k=1,matsize(f)[1],nextprime(1+f[k,1])^f[k,2]))
    
  • PARI
    a(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Michel Marcus, May 17 2014
    
  • Perl
    use ntheory ":all";  sub a003961 { vecprod(map { next_prime($) } factor(shift)); }  # _Dana Jacobsen, Mar 06 2016
    
  • Python
    from sympy import factorint, prime, primepi, prod
    def a(n):
        f=factorint(n)
        return 1 if n==1 else prod(prime(primepi(i) + 1)**f[i] for i in f)
    [a(n) for n in range(1, 11)] # Indranil Ghosh, May 13 2017

Formula

If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
Multiplicative with a(p^e) = A000040(A000720(p)+1)^e. - David W. Wilson, Aug 01 2001
a(n) = Product_{k=1..A001221(n)} A000040(A049084(A027748(n,k))+1)^A124010(n,k). - Reinhard Zumkeller, Oct 09 2011 [Corrected by Peter Munn, Nov 11 2019]
A064989(a(n)) = n and a(A064989(n)) = A000265(n). - Antti Karttunen, May 20 2014 & Nov 01 2019
A001221(a(n)) = A001221(n) and A001222(a(n)) = A001222(n). - Michel Marcus, Jun 13 2014
From Peter Munn, Oct 31 2019: (Start)
a(n) = A225546((A225546(n))^2).
a(A225546(n)) = A225546(n^2).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 2.06399637... . - Amiram Eldar, Nov 18 2022

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Original entry on oeis.org

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375
Offset: 1

Views

Author

David Petry (petry(AT)accessone.com)

Keywords

Comments

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

Examples

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).
		

Crossrefs

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

Programs

  • Mathematica
    fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
    Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)
  • PARI
    is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A091202 Factorization-preserving isomorphism from nonnegative integers to binary codes for polynomials over GF(2).

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 11, 8, 5, 14, 13, 12, 19, 22, 9, 16, 25, 10, 31, 28, 29, 26, 37, 24, 21, 38, 15, 44, 41, 18, 47, 32, 23, 50, 49, 20, 55, 62, 53, 56, 59, 58, 61, 52, 27, 74, 67, 48, 69, 42, 43, 76, 73, 30, 35, 88, 33, 82, 87, 36, 91, 94, 39, 64, 121, 46, 97, 100, 111, 98
Offset: 0

Views

Author

Antti Karttunen, Jan 03 2004

Keywords

Comments

E.g. we have the following identities: A000005(n) = A091220(a(n)), A001221(n) = A091221(a(n)), A001222(n) = A091222(a(n)), A008683(n) = A091219(a(n)), A014580(n) = a(A000040(n)), A049084(n) = A091227(a(n)).

Crossrefs

Inverse: A091203.
Several variants exist: A235041, A091204, A106442, A106444, A106446.
Cf. also A302023, A302025, A305417, A305427 for other similar permutations.

Programs

  • PARI
    A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };
    A305421(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305420(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
    A091202(n) = if(n<=1,n,if(!(n%2),2*A091202(n/2),A305421(A091202(A064989(n))))); \\ Antti Karttunen, Jun 10 2018

Formula

a(0)=0, a(1)=1, a(p_i) = A014580(i) for primes p_i with index i and for composites a(p_i * p_j * ...) = a(p_i) X a(p_j) X ..., where X stands for carryless multiplication of GF(2)[X] polynomials (A048720).
Other identities. For all n >= 1, the following holds:
A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091204, A106442, A106444, A106446, A235041 and A245703 have the same property.]
From Antti Karttunen, Jun 10 2018: (Start)
For n <= 1, a(n) = n, for n > 1, a(n) = 2*a(n/2) if n is even, and if n is odd, then a(n) = A305421(a(A064989(n))).
a(n) = A305417(A156552(n)) = A305427(A243071(n)).
(End)

A305422 GF(2)[X] factorization prime shift towards smaller terms.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 7, 2, 11, 3, 8, 1, 16, 6, 13, 4, 5, 7, 22, 2, 19, 11, 12, 3, 14, 8, 25, 1, 50, 16, 29, 6, 31, 13, 28, 4, 37, 5, 38, 7, 24, 22, 41, 2, 9, 19, 32, 11, 26, 12, 47, 3, 44, 14, 55, 8, 59, 25, 10, 1, 20, 50, 61, 16, 21, 29, 118, 6, 67, 31, 88, 13, 110, 28, 53, 4, 69, 37, 18, 5, 64, 38, 73, 7, 94, 24, 87, 22, 43, 41, 52, 2, 91
Offset: 1

Views

Author

Antti Karttunen, Jun 07 2018

Keywords

Comments

Let a x b stand for the carryless binary multiplication of positive integers a and b, that is, the result of operation A048720(a,b). With n having a unique factorization as f(i) x f(j) x ... x f(k), with 1 <= i <= j <= ... <= k, a(n) = f(i-1) x f(j-1) x ... x f(k-1), where f(0) = 1, and f(n) = A014580(n) for n >= 1.

Crossrefs

Cf. A000079 (positions of ones), A014580, A091225, A268389, A305419, A305421, A305424 (odd bisection), A305425.
Cf. also A064989, A300840.

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
    A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };

Formula

For all n >= 1:
a(A305421(n)) = n.
a(A001317(n)) = A000079(n).
A007814(a(n)) = A268389(n).

A305420 Smallest k > n whose binary expansion encodes an irreducible (0,1)-polynomial over GF(2)[X].

Original entry on oeis.org

2, 3, 7, 7, 7, 7, 11, 11, 11, 11, 13, 13, 19, 19, 19, 19, 19, 19, 25, 25, 25, 25, 25, 25, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 37, 37, 41, 41, 41, 41, 47, 47, 47, 47, 47, 47, 55, 55, 55, 55, 55, 55, 55, 55, 59, 59, 59, 59, 61, 61, 67, 67, 67, 67, 67, 67, 73, 73, 73, 73, 73, 73, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 91
Offset: 1

Views

Author

Antti Karttunen, Jun 07 2018

Keywords

Comments

a(n) is the smallest term of A014580 greater than n.

Crossrefs

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305420(n) = { my(k=1+n); while(!A091225(k),k++); (k); };

Formula

For n >= 1, a(n) = A091228(1+n).

A305425 a(n) = n/2 for even n, a(n) = A305422(n) for odd n.

Original entry on oeis.org

1, 1, 2, 2, 4, 3, 3, 4, 6, 5, 7, 6, 11, 7, 8, 8, 16, 9, 13, 10, 5, 11, 22, 12, 19, 13, 12, 14, 14, 15, 25, 16, 50, 17, 29, 18, 31, 19, 28, 20, 37, 21, 38, 22, 24, 23, 41, 24, 9, 25, 32, 26, 26, 27, 47, 28, 44, 29, 55, 30, 59, 31, 10, 32, 20, 33, 61, 34, 21, 35, 118, 36, 67, 37, 88, 38, 110, 39, 53, 40, 69, 41, 18, 42, 64, 43, 73, 44, 94, 45, 87, 46, 43, 47
Offset: 1

Views

Author

Antti Karttunen, Jun 08 2018

Keywords

Comments

Each k occurs exactly twice, at 2k and at A305421(k).

Crossrefs

Bisections: A000027 and A305422.
Cf. also A252463.

Programs

  • PARI
    A091225(n) = polisirreducible(Pol(binary(n))*Mod(1, 2));
    A305419(n) = if(n<3,1, my(k=n-1); while(k>1 && !A091225(k),k--); (k));
    A305422(n) = { my(f = subst(lift(factor(Pol(binary(n))*Mod(1, 2))),x,2)); for(i=1,#f~,f[i,1] = Pol(binary(A305419(f[i,1])))); fromdigits(Vec(factorback(f))%2,2); };
    A305425(n) = if(n%2,A305422(n),n/2);

Formula

a(n) = n/2 if n is even, a(n) = A305422(n) if n is odd.
Showing 1-9 of 9 results.