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.

Previous Showing 21-24 of 24 results.

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Original entry on oeis.org

15, 91, 703, 1891, 8911, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 5481451, 6186403, 6969511
Offset: 1

Views

Author

Amiram Eldar, Nov 20 2019

Keywords

Comments

Odd numbers k such that A071294((k-1)/2) = A000010(k)/4.
For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.
The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.

Examples

			15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.

References

  • Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.

Links

Crossrefs

Cf. A000010, A033181, A006945, A014233, A071294, A141768, A181782, A195328, A329468.
Cf. A001262, A020229, A020231, A020233.

Programs

  • Mathematica
    o[n_] := (n - 1)/2^IntegerExponent[n - 1, 2];
a[n_?PrimeQ] := n - 1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2] & /@ (p - 1)]) - 1)/(2^om - 1))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]

A363215 Integers p > 1 such that 3^d == 1 (mod p) where d = A000265(p-1).

Original entry on oeis.org

2, 11, 13, 23, 47, 59, 71, 83, 107, 109, 121, 131, 167, 179, 181, 191, 227, 229, 239, 251, 263, 277, 286, 311, 313, 347, 359, 383, 419, 421, 431, 433, 443, 467, 479, 491, 503, 541, 563, 587, 599, 601, 647, 659, 683, 709, 719, 733, 743, 757, 827, 829, 839, 863
Offset: 1

Views

Author

Jeppe Stig Nielsen, May 21 2023

Keywords

Comments

Inspired by an incorrect definition of strong pseudoprime to base 3.
As is obvious from the data, it fails to include all primes. Does include some composite numbers (pseudoprimes), namely 121, 286, 24046, 47197, 82513, ...

Links

Crossrefs

Cf. A000265, A005935, A020229, A130433.

Programs

  • PARI
    is(p)=my(d=p-1);d/=2^valuation(d,2);Mod(3,p)^d==1
  • Python
    from itertools import count, islice
def inA363215(n): return pow(3,n-1>>(~(n-1)&n-2).bit_length(),n)==1
def A363215_gen(startvalue=2): # generator of terms >= startvalue
    return filter(inA363215,count(max(startvalue,2)))
A363215_list = list(islice(A363215_gen(),20)) # Chai Wah Wu, May 22 2023

A140507 Numbers k such that 3^k-1 contains a divisor which is an overpseudoprime in base 3.

Original entry on oeis.org

5, 10, 11, 15, 16, 17, 18, 19, 20, 22, 23, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85
Offset: 1

Views

Author

Vladimir Shevelev, Jun 30 2008

Keywords

Comments

An odd prime p is in the sequence iff p is not in A028491.

Crossrefs

Cf. A141350, A020229, A141232, A141390, A003462, A028491.

Programs

  • PARI
    isokd(n) = (n!=1) && !isprime(n) && (gcd(n,3)==1) && (znorder(Mod(3,n)) * (sumdiv(n, d, eulerphi(d)/znorder(Mod(3, d))) - 1) + 1 == n); \\ A141350
isok(n) = {fordiv (3^n-1, d, if (isokd(d), return (1));); return (0);}

Extensions

More terms from Michel Marcus, Oct 25 2018

A298757 Numbers k with record value of the least strong pseudoprime to base k (A298756).

Original entry on oeis.org

2, 1320, 4712, 5628, 7252, 7852, 14787, 17340, 61380, 78750, 254923, 486605, 1804842, 4095086, 12772344, 42162995
Offset: 1

Views

Author

Amiram Eldar, Jan 26 2018

Keywords

Comments

The record strong pseudoprimes are 2047, 4097, 4711, 5627, 7251, 7851, 9409, 10261, 11359, 13747, 18299, 25761, 32761, 38323, 40501, 97921, ...

Links

Crossrefs

Cf. A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A298756.

Programs

  • Mathematica
    sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := Module[{ans=False},s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, ans=True, Do[If[PowerMod[b, d*2^r, n] == n-1, ans=True], {r, 0, s-1}]];ans]; smallestSPP[b_] := Module[ {k=3}, While[ !sppQ[k,b],k+=2];k ]; sm=0;a={};Do[s=smallestSPP[b];If[s>sm,sm=s;AppendTo[a,b]], {b,2,10^4}];a (* after Jean-François Alcover at A020229 *)
  • PARI
    lista(nn) = {my(m=0); for (n=2, nn, my(r=a298756(n)); if (r>m, m =r; print1(n, ", ")););} \\ Michel Marcus, Jan 31 2022; using pari code in A298756

Extensions

a(9)-a(16) from Jonathan Pappas, Jan 31 2022
Previous Showing 21-24 of 24 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.