A002326 -id:A002326 - cp's OEIS frontend

A137576 a(n) = A002326(n) * A006694(n) + 1.

1, 3, 5, 7, 13, 11, 13, 17, 17, 19, 31, 23, 41, 55, 29, 31, 41, 61, 37, 49, 41, 43, 85, 47, 85, 57, 53, 81, 73, 59, 61, 73, 73, 67, 111, 71, 73, 141, 151, 79, 217, 83, 89, 113, 89, 109, 131, 145, 97, 211, 101, 103, 169, 107, 109, 145, 113, 221, 133, 193, 221, 141, 301, 127

Offset: 0

Vladimir Shevelev, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008

nonn

Composite numbers n for which a((n-1)/2)=n are called overpseudoprimes to base 2 (A141232).
Theorem. If p and q are odd primes then the equality a((pq-1)/2)=pq is valid if and only if A002326((p-1)/2)=A002326((q-1)/2). Example: A002326(11) = A002326(44). Since 23 and 89 are primes then a((23*89-1)/2)=23*89.
A generalization: If p_1A002326((p_1-1)/2)= A002326((p_2-1)/2)=...=A002326((p_m-1)/2).
Moreover, if n is an odd squarefree number and a((n-1)/2)=n then also all divisors d of n satisfy a((d-1)/2)=d and d divides 2^d-2. Thus the sequence of such n is a subsequence of A050217.

Ray Chandler, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, Exact exponent of remainder term of Gelfond's digit theorem in binary case, arXiv:0804.3682 [math.NT], 2008.
Vladimir Shevelev, Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithmetica 136 (2009), 91-100.

Cf. A002326, A006694, A138193, A138217, A138227, A141232, A195468.

a[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Dec 04 2015, adapted from PARI *)

a(n)=my(t);sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1 \\ Charles R Greathouse IV, Feb 20 2013

It can be shown that if p is an odd prime then a((p^k-1)/2)=1+k*phi(p^k).

a(n) = ord(2,2*n+1) * ((Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1) + 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Edited and extended by Ray Chandler, May 08 2008

A292270 Sum of all partial fractions in the algorithm used for calculation of A002326(n).

Original entry on oeis.org

1, 1, 4, 1, 13, 25, 36, 1, 38, 81, 12, 26, 124, 121, 196, 1, 103, 73, 324, 42, 224, 175, 91, 147, 232, 14, 676, 170, 303, 841, 900, 1, 264, 1089, 385, 364, 93, 301, 585, 563, 1093, 1681, 44, 355, 152, 118, 83, 484, 1254, 763, 2500, 1043, 156, 2809, 996, 564, 952, 931, 71, 387, 3325, 176, 3124, 1, 649, 4225, 554, 1081

Offset: 0

Vladimir Shevelev and Antti Karttunen, Oct 05 2017

nonn

This sequence gives important additional insight into the algorithm for the calculation of A002326 (see A179680 for its description). Let us estimate how many steps are required before (the first) 1 will appear. Note that all partial fractions (which are indeed, integers) are odd residues modulo 2*n+1 from the interval [1,2*n-1]. So, if there is no repetition, then the number of steps does not exceed n. Suppose then that there is a repetition before the appearance of 1. Then for an odd residue k from [1, 2*n-1], 2^m_1 == 2^m_2 == k (mod 2*n+1) such that m_2 > m_1. But then 2^(m_2-m_1) == 1 (mod 2*n+1). So, since m_2 - m_1 < m_2, it means that 1 should appear earlier than the repetition of k, which is a contradiction. So the number of steps <= n. For example, for n=9, 2*n+1 = 19, we have exactly 9 steps with all other odd residues <= 17 modulo 19 appearing before the final 1: 5, 3, 11, 15, 17, 9, 7, 13, 1.

A001122 gives the odd numbers k such that a((k-1)/2) = A000290((k-1)/2).

			Let n = 9. According to the comment, a(9) = 5 + 3 + 11 + 15 + 17 + 9 + 7 + 13 + 1 = 81.

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

Cf. A000265, A000290, A001122, A001917, A002326, A006519, A163782, A179382, A179680, A292239, A292265, A292947, A293218, A293219.

Cf. A000225 (gives the positions of ones), A292938 (of squares), A292939 (and the corresponding odd numbers), A292940 (odd numbers corresponding to squares larger than one), A292379 (odd numbers corresponding to squares less than n^2).

A000265(n) = (n >> valuation(n, 2));
A006519(n) = 2^valuation(n, 2);
A292270(n) = { my(x = n+n+1, z = ((1+x)/A006519(1+x)), m = A000265(1+x)); while(m!=1, z += ((x+m)/A006519(x+m)); m = A000265(x+m)); z; };

(define (A292270 n) (let ((x (+ n n 1))) (let loop ((z (/ (+ 1 x) (A006519 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (+ z (/ (+ x m) (A006519 (+ x m)))) m))))))

For all n >= 1, A000196(a((A001122(1+n)-1)/2)) = (A001122(1+n)-1)/2, in other words, a(A163782(n)) = A000290(A163782(n)).

A165781 a(n) = (2^A002326(n)-1)/(2*n+1).

Original entry on oeis.org

1, 1, 3, 1, 7, 93, 315, 1, 15, 13797, 3, 89, 41943, 9709, 9256395, 1, 31, 117, 1857283155, 105, 25575, 381, 91, 178481, 42799, 5, 84973577874915, 19065, 4599, 4885260612740877, 18900352534538475, 1, 63, 1101298153654301589

Offset: 0

Ctibor O. Zizka, Sep 26 2009

a(n) = 1 <=> n is in A000225 <=> n = 2^k - 1 with k = 0, 1, 2, ... - M. F. Hasler, Sep 20 2017

Robert Israel, Table of n, a(n) for n = 0..1672

Cf. A002326, A053446, A000225.

A002326 := proc(n) if n = 0 then 1 ; else numtheory[order](2,2*n+1) ; end if ; end proc:
A165781 := proc(n) (2^A002326(n)-1)/(2*n+1) ; end proc:
seq(A165781(n),n=0..60) ; # R. J. Mathar, Nov 16 2009

a[n_] := (2^MultiplicativeOrder[2, 2n+1]-1)/(2n+1);
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2020 *)

a(n)=(2^znorder(Mod(2,n=2*n+1))-1)/n \\ M. F. Hasler, Sep 20 2017

Sign in definition and offset corrected by R. J. Mathar, Nov 16 2009

A182297 Wieferich numbers (2): positive odd integers q such that q and (2^A002326((q-1)/2)-1)/q are not relatively prime.

Original entry on oeis.org

21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, 195, 201, 203, 205, 219, 231, 237, 253, 273, 285, 291, 301, 305, 309, 327, 333, 355, 357, 385, 399, 417, 429, 453, 465, 483, 489, 495, 497, 505, 507, 525, 543, 555, 579, 597, 605, 609, 615, 627, 633, 651, 655

Offset: 1

Felix Fröhlich, Apr 23 2012

nonn

The primes in this sequence are A001220, the Wieferich primes. - Charles R Greathouse IV, Feb 02 2014

Odd prime p is a Wieferich prime if and only if A002326((p^2-1)/2) = A002326((p-1)/2). See the sixth comment to A001220 and my formula below. - Thomas Ordowski, Feb 03 2014

			21 is in the sequence because the multiplicative order of 2 mod 21 is 6, and (2^6-1)/21 = 3, which is not coprime to 21.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Z. Franco and C. Pomerance, On a conjecture of Crandall concerning the qx + 1 problem, Math. Comp. Vol. 64, No. 211 (1995), 1333-1336.

For another definition of Wieferich numbers, see A077816.

Cf. A002326.

with(numtheory):
a:= proc(n) option remember; local q;
      for q from 2 +`if`(n=1, 1, a(n-1)) by 2
        while igcd((2^order(2, q)-1)/q, q)=1 do od; q
    end:
seq (a(n), n=1..60);  # Alois P. Heinz, Apr 23 2012

Select[Range[1, 799, 2], GCD[#, (2^MultiplicativeOrder[2, #] - 1)/#] > 1 &] (* Alonso del Arte, Apr 23 2012 *)

is(n)=n%2 && gcd(lift(Mod(2,n^2)^znorder(Mod(2,n))-1)/n,n)>1 \\ Charles R Greathouse IV, Feb 02 2014

Odd numbers q such that A002326((q^2-1)/2) < q * A002326((q-1)/2). Other positive odd integers satisfy the equality. - Thomas Ordowski, Feb 03 2014

Odd numbers q such that gcd(A165781((q-1)/2), q) > 1. - Thomas Ordowski, Feb 12 2014

A292239 A multiplicative encoding for the exponents of 2 obtained when using Shevelev's algorithm for computing A002326.

Original entry on oeis.org

2, 3, 10, 5, 28, 252, 840, 7, 88, 23760, 22, 330, 66528, 23760, 6652800, 11, 208, 468, 471744000, 390, 58240, 1872, 468, 163800, 93600, 39, 3736212480000, 39000, 17472, 94152554496000, 313841848320000, 13, 544, 7387354275840000, 146880, 84823200, 68, 36720, 12337920, 1079568000

Offset: 0

Antti Karttunen, Oct 02 2017

nonn

a(n) = prime(v(1)) * prime(v(2)) * ... * prime(v(k)), where prime(n) is the n-th prime (= A000040(n)) and v(1) .. v(k) are 2-adic valuations (not all necessarily distinct) of the iterated values obtained when running Shevelev's algorithm for computing A002326. See comments in A179680 and compare to A292265.

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

Cf. A000040, A000265, A002326, A007814, A179382, A179680, A292265 (a variant).

a265[n_] := n/2^IntegerExponent[n, 2];
a[n_] := Module[{x, z, m}, x = 2 n + 1; z = Prime[IntegerExponent[1 + x, 2]]; m = a265[1 + x]; While[m != 1, z *= Prime[IntegerExponent[x + m, 2]]; m = a265[x + m]]; z];
Table[a[n], {n, 0, 39}] (* Jean-François Alcover, Oct 03 2017, translated from PARI *)

A000265(n) = (n >> valuation(n, 2));
A292239(n) = { my(x = n+n+1, z = prime(valuation(1+x,2)), m = A000265(1+x)); while(m!=1, z *= prime(valuation(x+m,2)); m = A000265(x+m)); z; };

(define (A292239 n) (let ((x (+ n n 1))) (let loop ((z (A000040 (A007814 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (* z (A000040 (A007814 (+ x m)))) m))))))

For all n >= 0:
A001222(a(n)) = A179382(1+n).
A056239(a(n)) = A002326(n).

A292265 A multiplicative encoding (compressed) for the exponents of 2 obtained when using Shevelev's algorithm for computing A002326.

Original entry on oeis.org

2, 3, 12, 6, 20, 180, 720, 5, 80, 25920, 20, 360, 43200, 25920, 6220800, 10, 240, 540, 671846400, 540, 57600, 2160, 540, 194400, 155520, 45, 5804752896000, 77760, 14400, 87071293440000, 348285173760000, 15, 960, 12538266255360000, 311040, 139968000, 120, 77760, 18662400, 1679616000, 23219011584000, 108330620446310400000, 60, 4665600, 360, 540, 180

Offset: 0

Antti Karttunen, Oct 02 2017

nonn

a(n) = A019565(v(1)) * A019565(v(2)) * ... * A019565(v(k)), where v(1) .. v(k) are 2-adic valuations (not all necessarily distinct) of the iterated values obtained when running Shevelev's algorithm for computing A002623. (See A179680 and A292239.)

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

Cf. A000265, A002326, A007814, A019565, A179680, A292239 (a variant), A292266 (rgs-version of this filter).

A000265(n) = (n >> valuation(n, 2));
A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ This function from M. F. Hasler
A292265(n) = { my(x = n+n+1, z = A019565(valuation(1+x,2)), m = A000265(1+x)); while(m!=1, z *= A019565(valuation(x+m,2)); m = A000265(x+m)); z; };

(define (A292265 n) (let ((x (+ n n 1))) (let loop ((z (A019565 (A007814 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (* z (A019565 (A007814 (+ x m)))) m))))))

For all n >= 0, A048675(a(n)) = A002326(n).

A139099 Numbers 2n+1 for which A002326(n) are record values of A002326.

Original entry on oeis.org

1, 3, 5, 9, 11, 13, 19, 25, 29, 37, 53, 59, 61, 67, 83, 101, 107, 121, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701

Offset: 1

Vladimir Shevelev, Jun 05 2008

nonn

Question: does this sequence contain infinitely many composite numbers?

Nonprimes in the sequence are 1, 9, 25, 121, 1369,... (no more up to at least 100000). [R. J. Mathar, Jul 14 2010]

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A002326, A001122.

a[n_] := MultiplicativeOrder[2, 2 n + 1]; s = {}; am = 0; Do[a1 = a[n]; If[a1 > am, am = a1; AppendTo[s, 2 n + 1]], {n, 0, 360}]; s (* Amiram Eldar, Sep 12 2019 *)

More terms from R. J. Mathar, Jul 14 2010

A291755 Compound filter (multiplicative order of 2 mod 2n+1 & eulerphi(2n+1)): a(n) = P(A002326(n), A037225(n)), where P(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

1, 5, 25, 31, 61, 181, 265, 59, 261, 613, 142, 507, 761, 613, 1513, 566, 416, 607, 2521, 607, 1731, 1499, 607, 2301, 1912, 749, 5305, 1731, 1396, 6613, 7081, 826, 1723, 8581, 2102, 5391, 3169, 1731, 3946, 6709, 5725, 13285, 2493, 3431, 4764, 3415, 2356, 5707, 10201, 3946, 19801, 11527

Offset: 0

Antti Karttunen, Oct 02 2017

nonn

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

Cf. A000010, A000027, A002326, A037225, A291766 (rgs-version of this filter).
Cf. also A292249, A292268.
Cf. A037226, A053006.

A002326[n_] := MultiplicativeOrder[2, 2n+1];
a[n_] := (1/2)*(2 + ((A002326[n] + EulerPhi[2n+1])^2) - A002326[n] - 3* EulerPhi[2n+1]);
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 23 2024 *)

A002326(n) = if(n<0, 0, znorder(Mod(2, 2*n+1))); \\ This function from Michael Somos, Mar 31 2005
A291755(n) = (1/2)*(2 + ((A002326(n)+eulerphi(n+n+1))^2) - A002326(n) - 3*eulerphi(n+n+1));

(define (A291755 n) (* 1/2 (+ (expt (+ (A002326 n) (A000010 (+ 1 n n))) 2) (- (A002326 n)) (- (* 3 (A000010 (+ 1 n n)))) 2)))

a(n) = (1/2)*(2 + ((A002326(n) + A000010(2n+1))^2) - A002326(n) - 3*A000010(2n+1)).

A291766 Restricted growth sequence transform of A291755; filter combining multiplicative order of 2 mod 2n+1 & eulerphi(2n+1) (A002326 & A037225).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 10, 14, 15, 16, 17, 18, 17, 19, 20, 17, 21, 22, 23, 24, 19, 25, 26, 27, 28, 29, 30, 31, 32, 33, 19, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 34, 45, 46, 29, 47, 48, 43, 49, 50, 41, 51, 52, 53, 45, 54, 55, 56, 57, 43, 58, 59, 60, 61, 49, 62, 63, 64, 51, 65, 66, 67, 68, 69, 53, 70, 71, 57, 72, 61, 73, 74, 75, 61

Offset: 0

Antti Karttunen, Oct 02 2017

nonn

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

Cf. A000010, A002326, A037225, A291755.
Cf. A291769, A292267 for related filters.
Cf. A037226, A053006.

rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A002326(n) = if(n<0, 0, znorder(Mod(2, 2*n+1))); \\ This function from Michael Somos, Mar 31 2005
A291755(n) = (1/2)*(2 + ((A002326(n)+eulerphi(n+n+1))^2) - A002326(n) - 3*eulerphi(n+n+1));
write_to_bfile(0,rgs_transform(vector(32769,n,A291755(n-1))),"b291766_upto32768.txt");

A291769 Restricted growth sequence transform of A292249; filter combining multiplicative order of 2 mod 2n+1 & prime signature of 2n+1 (A002326 & A278223).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 18, 32, 33, 34, 35, 36, 37, 38, 39, 40, 25, 41, 12, 18, 17, 42, 43, 44, 45, 46, 47, 48, 19, 42, 15, 49, 22, 50, 51, 27, 52, 53, 54, 55, 28, 56, 57, 58, 59, 60, 41, 61, 62, 63, 64, 27, 26, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 60, 42

Offset: 0

Antti Karttunen, Oct 02 2017

nonn

Also restricted growth sequence transform of the odd bisection of A286573.

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

Cf. A002326, A046523, A278223, A286573, A291766, A292249.

Cf. A291766, A292267 for related filters.

rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A002326(n) = if(n<0, 0, znorder(Mod(2, 2*n+1))); \\ This function from Michael Somos, Mar 31 2005
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A292249(n) = (1/2)*(2 + ((A002326(n)+A046523(n+n+1))^2) - A002326(n) - 3*A046523(n+n+1));
write_to_bfile(0,rgs_transform(vector(32769,n,A292249(n-1))),"b291769_upto32768.txt");

cp's OEIS Frontend

A137576 a(n) = A002326(n) * A006694(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A292270 Sum of all partial fractions in the algorithm used for calculation of A002326(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

A165781 a(n) = (2^A002326(n)-1)/(2*n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A182297 Wieferich numbers (2): positive odd integers q such that q and (2^A002326((q-1)/2)-1)/q are not relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A292239 A multiplicative encoding for the exponents of 2 obtained when using Shevelev's algorithm for computing A002326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A292265 A multiplicative encoding (compressed) for the exponents of 2 obtained when using Shevelev's algorithm for computing A002326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A139099 Numbers 2n+1 for which A002326(n) are record values of A002326.

Views

Author

Keywords

Comments

Links

Crossrefs