A242139 -id:A242139 - cp's OEIS frontend

A245583 Wieferich prime candidates: primes of the form A242139(n)+1 also having the form {m*(2^rs - 1)/(2^r - 1)}+1.

293, 439, 547, 1093, 1171, 2341, 3511

Offset: 1

Felix Fröhlich, Jul 26 2014

292 = 100100100, 438 = 110110110, 546 = 001000100010, 1092 = 010001000100, 1170 = 010010010010, 2340 = 100100100100, 3510 = 110110110110.
According to Dobson, all primes where m is of the form 2*(4^(r/2)-1)/3 cannot be Wieferich primes.
Triples (m, r, s) producing the terms through the formula in definition are (4, 3, 3), (6, 3, 3), (2, 4, 3), (4, 4, 3), (2, 3, 4), (4, 3, 4), (6, 3, 4).

S. Agou, Irréductibilité des polynômes f(X^p^r-aX) sur un corps fini F_p^s, J. reine angew. Mat. 292 (1977), 191-195.
J. B. Dobson, A note on the two known Wieferich primes (Archive of the site from August 28 2011)

Cf. A001220, A242139.

A240719 Numbers k such that 2^k == 1 (mod (k+1)^2).

Original entry on oeis.org

1092, 3510

Offset: 1

Felix Fröhlich, Apr 11 2014

There are only two known terms.
If p is in A001220, then p-1 is in the sequence. If k is in the sequence and k+1 is composite, then any prime factor of k+1 is in A001220 (see fifth comment for a proof). In that case, k+1 could be called a 'Wieferich pseudoprime'.
Any further terms are greater than 1.2 * 10^17. - Charles R Greathouse IV, Apr 12 2014
Both known terms have a periodic binary representation (i.e., 1092 = 010001000100, 3510 = 110110110110), so they are terms of A242139. Also, the ratio between those numbers and their divisor sums is 112/39 in both cases (see Dobson's website in the links and also A239875). Are those facts just coincidences? - Felix Fröhlich, Apr 15 2014
Proof of second part of second comment above: Let q be any odd prime factor of (k+1). Since 2 and q^2 are coprime, it follows from Euler's totient theorem (also known as Euler's theorem or Fermat-Euler theorem) that 2^(phi(q^2)) == 1 (mod q^2). Writing phi(q^2) = q^2 - q = q(q-1), one gets 2^(q(q-1)) == 1 (mod q^2). Taking the q-th root of both sides of the congruence yields 2^(q-1) == 1 (mod q^2). Q.E.D. - Felix Fröhlich, Jun 08 2015
If a(3) exists, it corresponds to A001220(3) - 1, i.e., a(3) + 1 must be prime. This can be shown the following way: Assume that a(3) + 1 is composite. Then the theorem from previous comment implies that a(3) + 1 is of the form 1093^x * 3511^y for some x, y >= 0 and x, y not both 0. If x or y is an integer k > 1, then p = 1093 or p = 3511 satisfies 2^(p-1) == 1 (mod p^(2k)). A quick check with PARI shows that neither 1093 nor 3511 satisfies this congruence for any k > 1. This leaves the case where x = y = 1, which can be excluded as well, since 3837523 is not in A001567. Q.E.D. - Felix Fröhlich, Jun 08 2015

J. Dobes and M. Kures, Search for Wieferich primes through the use of periodic binary strings, Serdica J. Computing, Volume 4, Number 3, 2010, 293-300.
J. B. Dobson, A note on the two known Wieferich primes
W. Johnson, On the nonvanishing of Fermat quotients (mod p), J. reine angew. Math., Issue 292 (Jan 1977), 196-200.
L. C. Washington, On Fermat's last theorem, J. reine angew. Math., Issue 289 (Jan 1977), 115-117.

Cf. A001220, A239875.

fQ[n_] := PowerMod[2, n, (n + 1)^2] == 1; Select[ Range@ 3600, fQ] (* Robert G. Wilson v, Jun 17 2015 *)

isok(n) = lift(Mod(2, (n+1)^2)^n) == 1; \\ Michel Marcus, Apr 12 2014

test(lim)=my(t=1); for(i=0, log(lim)\log(1093), my(n=t); while(n<=lim, if(Mod(2,n^2)^(n-1)==1&&n>1, print(n-1)); n*=3511); t*=1093)
test(1.2e17) \\ Test up to the current search bound for Wieferich primes; Charles R Greathouse IV, Apr 12 2014

A242138 Binary representation of periodic binary numbers, ordered by their decimal values.

Original entry on oeis.org

101, 1001, 1010, 10001, 10010, 10101, 11011, 100001, 100010, 100100, 101010, 101101, 110011, 110110, 1000001, 1000010, 1000100, 1001001, 1010101, 1100011, 1100110, 1110111, 10000001, 10000010, 10000100, 10001000, 10010010, 10011001, 10100101, 10101010

Offset: 1

Felix Fröhlich, May 05 2014

The numbers must contain both 0's and 1's.

Some of these numbers only become periodic if the leading zeros of their fundamental periods are appended to the front of their binary representations. For example, the first two terms are in this sequence, because with leading zeros they become 0101 and 001001, respectively.

Cf. A242139.

lista(nn) = for(n=1, nn, if (isA242139(n), print1(subst(Pol(binary(n), x), x, 10), ", "));); \\ Michel Marcus, Aug 25 2014

Inserted missing terms 1100011, 1100110, 1110111 and more terms, Michel Marcus, Aug 25 2014

A321513 Numbers that are periodic in base 4, written in decimal, where the base-4 expansion contains at least two periods.

Original entry on oeis.org

5, 10, 15, 17, 21, 34, 42, 51, 63, 65, 68, 85, 102, 119, 130, 136, 153, 170, 187, 195, 204, 221, 238, 255, 257, 260, 273, 325, 341, 390, 455, 514, 520, 546, 585, 650, 682, 715, 771, 780, 819, 845, 910, 975, 1023, 1025, 1028, 1040, 1092, 1105, 1170, 1235, 1285

Offset: 1

Felix Fröhlich, Nov 11 2018

			The base-4 representation of 17 is 101, which is periodic when considering leading zeros, i.e., 0101, so 17 is a term of the sequence.
The base-4 representation of 170 is 2222, which is periodic, so 170 is a term of the sequence.
The base-4 representation of 1495 is 113113, which is periodic, so 1495 is a term of the sequence.

Cf. A007090, A242139.

subvec(vec, pos, len) = my(w=[]); for(k=pos, pos+len-1, if(k > #vec, return(0), w=concat(w, vec[k]))); w
is_perio(vec) = my(d=divisors(#vec), v=[], w=[]); for(x=2, #d-1, v=subvec(vec, 1, d[x]); forstep(y=1, #vec, d[x], w=subvec(vec, y, d[x]); if(w!=v, break, if(y+d[x] >= #vec, return(1))))); 0
is(n) = my(d=digits(n, 4), z=[]); if(#d < 2, return(0)); if(vecmin(d)==vecmax(d), return(1)); while(#z <= #d, if(is_perio(concat(z, d)), return(1)); z=concat(z, [0])); 0

is(n, b=4) = for (w=1, oo, my (d=digits(n, b^w)); if (#d<=1, return (0), #Set(d)==1, return (1))) \\ Rémy Sigrist, Nov 16 2018

A353339 Number of integers b with n > b > 1 such that the base-b representation of n is periodic.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 2, 2, 2, 4, 1, 2, 2, 2, 3, 2, 3, 4, 1, 3, 4, 2, 1, 4, 1, 4, 3, 4, 1, 4, 3, 3, 3, 4, 2, 5, 2, 2, 2, 5, 1, 5, 2, 3, 4, 2, 1, 5, 1, 5, 4, 4, 1, 5, 2, 4, 3, 2, 1, 7, 1, 3, 5, 3, 5, 5, 1, 5, 2, 5, 1, 5, 3, 3, 3, 3, 2, 5, 1, 6, 2, 4, 1, 7, 4, 3, 2

Offset: 1

Felix Fröhlich, Apr 14 2022

			For n = 10: The base-2, base-3, base-4 and base-9 representations of 10 are 1010, 0101, 22 and 11, respectively, and these are the only representations that are periodic, so a(10) = 4.

Cf. A121016, A242138, A242139, A321513.

is(n, b) = for (w=1, oo, my (d=digits(n, b^w)); if (#d<=1, return (0), #Set(d)==1, return (1))) \\ after Rémy Sigrist in A321513
a(n) = my(i=0); for(b=2, n-1, if(is(n, b), i++)); i

A352886 Number of B-periodic numbers of bit pseudo-length n.

Original entry on oeis.org

1, 0, 4, 0, 7, 3, 16, 0, 37, 0, 64, 18, 127, 0, 283, 0, 517, 66, 1024, 0, 2167, 15, 4096, 255, 8197, 0, 16906, 0, 32767, 1026, 65536, 78, 133087, 0, 262144, 4098, 524407, 0, 1056730, 0, 2097157, 16635, 4194304, 0, 8421247, 63, 16777711, 65538, 33554437, 0

Offset: 4

Felix Fröhlich, Apr 07 2022

For the definition of "B-periodic numbers" and "bit pseudo-length", see Dobeš, Kureš, 2010, p. 294. The first few terms are given in the table on p. 295.

The sequence counts periodic binary numbers of length n where the least-significant bit is 0 (see Dobeš, Kureš, 2010, p. 294).

			For n = 6: The B-periodic numbers of bit pseudo-length 6 are 101010, 100100, 010010 and 110110, so a(6) = 4.

J. Dobeš and M. Kureš, Search for Wieferich Primes through the use of Periodic Binary Strings, Serdica Journal of Computing, Vol. 4, No. 3 (2010), 293-300.

Cf. A008683, A027375, A242138, A242139.

c(n) = sumdiv(n, d, moebius(d)*2^(n/d))
a(n) = (2^n - c(n) - 2)/2

a(n) = (2^n - c(n) - 2)/2, where c(n) = Sum_{d|n} A008683(d)*2^(n/d).

cp's OEIS Frontend

A245583 Wieferich prime candidates: primes of the form A242139(n)+1 also having the form {m*(2^rs - 1)/(2^r - 1)}+1.

Views

Author

Keywords

Comments

Links

Crossrefs

A240719 Numbers k such that 2^k == 1 (mod (k+1)^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A242138 Binary representation of periodic binary numbers, ordered by their decimal values.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A321513 Numbers that are periodic in base 4, written in decimal, where the base-4 expansion contains at least two periods.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

A353339 Number of integers b with n > b > 1 such that the base-b representation of n is periodic.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A352886 Number of B-periodic numbers of bit pseudo-length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula