A136474 -id:A136474 - cp's OEIS frontend

A057719 Prime factors of numbers in A006521 (numbers k that divide 2^k + 1).

3, 19, 163, 571, 1459, 8803, 9137, 17497, 41113, 52489, 78787, 87211, 135433, 139483, 144667, 164617, 174763, 196579, 274081, 370009, 370387, 478243, 760267, 941489, 944803, 1041619, 1220347, 1236787, 1319323, 1465129, 1663579, 1994659

Offset: 1

Ignacio Larrosa Cañestro, Oct 26 2000

nonn

A prime p is in this sequence iff all prime divisors of ord_p(2)/2 are in this sequence, where ord_p(2) is the order of 2 modulo p. - Max Alekseyev, Jul 30 2006

			2^171 + 1 == 0 (mod 171), 171 = 3^2*19, 2^13203+1 == 0 (mod 13203), 13203 = 3^4*163.

Joerg Arndt, Table of n, a(n) for n = 1..220 (terms up to 10^9, terms for n = 1..100 from T. D. Noe)
Alexander Kalmynin, On Novák numbers, arXiv:1611.00417 [math.NT], 2016. See Chapter 4 p. 7 Novák primes.
C. Smyth, The terms in Lucas Sequences divisible by their indices, JIS 13 (2010) #10.2.4.

Cf. A006521, A066364.

Cf. A136474, A136473.

S = {2}; Reap[For[p = 3, p < 2 10^6, p = NextPrime[p], f = FactorInteger[ MultiplicativeOrder[2, p]]; If[f[[1, 1]] != 2 || f[[1, 2]] != 1, Continue[]]; f = f[[All, 1]]; If[Length[Intersection[S, f]] == Length[f], S = Union[S, {p}]; Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Nov 11 2018, from PARI *)

{ A057719() = local(S,f); S=Set([2]); forprime(p=3,10^7, f=factorint(znorder(Mod(2,p))); if(f[1,1]!=2||f[1,2]!=1,next); f=f[,1]; if(length(setintersect(S,Set(f)))==length(f), S=setunion(S,[p]); print1(p,", "))) }

Edited by Max Alekseyev, Jul 30 2006

A136473 Primitive elements of the sequence of integers n such that n divides 2^n + 1 (A006521).

Original entry on oeis.org

1, 3, 171, 13203, 97641, 354537, 2354697, 10970073, 29884473, 33894369, 38265939, 74214171, 116226009, 344380329, 751611177, 892145817, 2595432537, 4014314433, 10161972027, 11852199369, 13229694441, 22032887841, 22230967347, 22864359897, 24020090001, 26761542921, 27439598619, 27932906619, 37498011939, 166111451217, 189836046171

Offset: 1

Toby Bailey and Christopher J. Smyth, Jan 13 2008

nonn

This gives a sparse subsequence of the sequence A006521 of all integers n such that n | 2^n+1. An element of A006521 is said to be *primitive* if it is not divisible by any smaller element of A006521 having the same prime divisors and further it is not the lcm of any two smaller elements of A006521. See Proposition 1 of the link.

Every element of this sequence apart from 1 and 3 is divisible either by 27 or by 171. Stronger results hold. For instance, every element of this sequence apart from 1 and 3 is divisible either by 171 or 243 or 13203 or 2354697 or 10970073 or 22032887841. See the link or A136475 for more details about such results. These alternative factors enable the sequence to be generated much more quickly than by the short Maple program given below.

			9 is in A006521 but is not primitive because its set of prime divisors is the same as that of 3, which divides 9 and is in A006521.
250857 is in A006521 but not primitive, as 250857=lcm(171,13203) and both 171 and 13203 are in A006521.

Max Alekseyev, Table of n, a(n) for n = 1..41
Toby Bailey and Chris Smyth, Primitive solutions of n|2^n+1.

Cf. A006521, A136474, A136475.

L:=1: S:={}: for j from 3 by 6 to 10^7 do if not 2&^j+1 mod j = 0 then next end if; if not (j in S) then L := L,j end if; S := S union map( ilcm, S, j ) union {j}; S := S union map(`*`, {map2( op, 1, ifactors(j)[2] )[]}, j); end do: L;

More terms from Max Alekseyev, Aug 04 2011

A136475 Irregular triangle read by rows: row n gives prime factors of (2^(3^(n+1))+1)/(2^(3^n)+1).

Original entry on oeis.org

3, 3, 19, 3, 87211, 3, 163, 135433, 272010961, 3, 1459, 139483, 10429407431911334611, 918125051602568899753, 3, 227862073, 3110690934667, 216892513252489863991753, 1102099161075964924744009, 393063301203384521164229656203691748263012766081190297429488962985651210769817

Offset: 0

Christopher J. Smyth, Feb 16 2008

The motivation for this sequence is to quickly generate integers n such that n divides 2^n+1 (sequences A006521, A136473). From the link, it is known that if 3^k||n with n|2^n+1 and n not a power of 3, then n is divisible by a prime p dividing 2^(3^k)+1. Thus for any fixed k every n with n|2^n+1 not a power of 3 is divisible by one of the following numbers: 3^k or some 3^j*p, where p>3 is a prime in A136475 before the k-th '3' and j is the number of '3's before p in the sequence.
Note: (2^(3^(k+1))+1)/(2^(3^k)+1) = 2^(2*3^k) - 2^(3^k) + 1.
For the primes dividing 2^(3^k)+1 for some k see A136474.
Are these numbers always squarefree?

			1. (2^(3^4)+1)/(2^(3^3)+1) = 3*163*135433*272010961, the factorization starting at the 4th '3' and ending just before the 5th '3'.
2. From Comment 1 below and k=5, we see that every n not a power of 3 satisfying n|2^n+1 (sequences A006521, A136473) is divisible by 3^5 or 3^2*19 or 3^3*87211 or 3^4*163 or 3^4*135433 or 3^4*272010961.

Toby Bailey and Chris Smyth Primitive solutions of n|2^n+1.(This is the same link as at A136473.)
S. S. Wagstaff, Jr., The Cunningham Project

Cf. A006521, A136473, A136474.

S:=[];for k from 0 to 4 do f:=op(2,ifactors((2^(3^(k+1))+1)/(2^(3^k)+1)));T:=[];for j to nops(f) do T:=[op(T),op(1,op(j,f))];od;S:=[op(S),op(sort(T))];od;op(S);

The prime factors of (2^(3^(k+1))+1)/(2^(3^k)+1) are given in ascending order *for each k*. For each new value of k the factorization starts with a '3', thus delimiting the different factorizations.

cp's OEIS Frontend

A057719 Prime factors of numbers in A006521 (numbers k that divide 2^k + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A136473 Primitive elements of the sequence of integers n such that n divides 2^n + 1 (A006521).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A136475 Irregular triangle read by rows: row n gives prime factors of (2^(3^(n+1))+1)/(2^(3^n)+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula