A036259 -id:A036259 - cp's OEIS frontend

A053006 Numbers m for which there exist d(1),...,d(m), each in {0,1}, such that Sum_{i=1..m-k} d(i)*d(i+k) is odd for all k=0,...,m-1.

1, 4, 12, 16, 24, 25, 36, 37, 40, 45, 52, 64, 76, 81, 84, 96, 100, 109, 112, 117, 120, 132, 136, 156, 165, 169, 172, 180, 184, 192, 216, 220, 232, 240, 244, 249, 252, 256, 265, 277, 300, 301, 304, 312, 316, 324, 357, 360, 361, 364, 372, 376, 412, 420, 432

Offset: 1

N. J. A. Sloane

m is in the sequence if and only if the multiplicative order of 2 (mod 2m-1) is odd.

R. K. Guy, Unsolved Problems in Number Theory, E38.

Amiram Eldar, Table of n, a(n) for n = 1..10000
P. Alles, On a Conjecture of J. Pelikan, J. Comb. Th. A 60 (1992) 312-313.
N. F. J. Inglis and J. D. A. Wiseman, Very odd sequences, J. Comb. Th. A 71 (1995) 89-96.
F. J. MacWilliams and A. M. Odlyzko, Pelikan's conjecture and cyclotomic cosets, J. Comb. Th. A 22 (1977) 110-114.

Cf. A000265, A036259.

o2[ m_ ] := Module[ {e, t}, For[ e = 1; t = 2, Mod[ t-1, m ] >0, e++, t = Mod[ 2t, m ] ]; e ]; Select[ Range[ 1, 500 ], OddQ[ o2[ 2#-1 ] ] & ]
(* Second program: *)
(Select[Range[1, 999, 2], OddQ[MultiplicativeOrder[2, #]]&] + 1)/2 (* Jean-François Alcover, Dec 20 2017 *)

is(n)=znorder(Mod(2,2*n-1))%2 \\ Charles R Greathouse IV, Jun 24 2015

A000265(n)=n>>valuation(n,2)
is(n)=Mod(2,2*n-1)^A000265(eulerphi(2*n-1))==1 \\ Charles R Greathouse IV, Jun 24 2015

from sympy import n_order
def A053006_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:n_order(2,(n<<1)-1)&1,count(max(startvalue,1)))
A053006_list = list(islice(A053006_gen(),20)) # Chai Wah Wu, Feb 07 2023

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

More terms from John W. Layman, Feb 21 2000

Additional information from Dean Hickerson, May 25 2001

A296243 Numbers k such that the multiplicative order of 2 modulo k is even.

Original entry on oeis.org

3, 5, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 33, 35, 37, 39, 41, 43, 45, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 75, 77, 81, 83, 85, 87, 91, 93, 95, 97, 99, 101, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 153

Offset: 1

Max Alekseyev, Dec 09 2017

nonn

Odd numbers k such that A007733(k) = A002326((k-1)/2) is even.

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

Set difference of A005408 and A036259.
Contains A296244 as a subsequence.
The prime terms are given by A014662.
Cf. A002326, A007733.

A036259 = Select[Range[1, 199, 2], OddQ[MultiplicativeOrder[2, #]] &];
Range[1, A036259[[-1]], 2] ~Complement~ A036259 (* Jean-François Alcover, Dec 20 2017 *)
Select[Range[1, 153, 2], EvenQ[MultiplicativeOrder[2, #]] &] (* Amiram Eldar, Jul 30 2020 *)

{ is_A296243(n) = (n%2) && !(znorder(Mod(2,n))%2); }

A036260 Numbers k > 1 such that k mod ord2(k) is even, where ord2(k) is the order of 2 mod k.

Original entry on oeis.org

2921, 3017, 3473, 3479, 5767, 5969, 6167, 6377, 6497, 6913, 7223, 7519, 7567, 7751, 9017, 9271, 10199, 10447, 11431, 11929, 12719, 13439, 13609, 14513, 16583, 17009, 17143, 18631, 18809, 19313, 20737, 21119, 22337, 22351, 22537

Offset: 1

David W. Wilson

nonn

These are all composite since for prime p, ord2(p) | phi(p) = p-1, whence p mod ord2(p) = 1.

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

Cf. A002326, A007733, A036259.

Select[Range[3, 23000, 2], EvenQ[Mod[#, MultiplicativeOrder[2, #]]] &] (* Amiram Eldar, Jul 30 2020 *)

Offset corrected by Amiram Eldar, Jul 30 2020

A367230 Base-2 Fermat pseudoprimes k such that the multiplicative order of 2 modulo k is odd.

Original entry on oeis.org

2047, 4681, 15841, 42799, 52633, 90751, 220729, 256999, 271951, 486737, 514447, 647089, 741751, 916327, 1082401, 1145257, 1730977, 1969417, 2205967, 2304167, 2748023, 2811271, 2953711, 2976487, 3567481, 4188889, 4469471, 4835209, 4863127, 5016191, 5049001, 5681809

Offset: 1

Amiram Eldar, Nov 11 2023

nonn

The corresponding sequence for primes is A014663.
These pseudoprimes seem to be relatively rare: among the 118968378 base-2 Fermat pseudoprimes below 2^64 only 6292535 are terms of this sequence.
These pseudoprimes appear in a theorem by Rotkiewicz and Makowski (1966) about pseudoprimes that are products of two Mersenne numbers (see A367229).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Andrzej Rotkiewicz and Andrzej Makowski, On Pseudoprime Numbers of the Form M_p M_t, Elemente der Mathematik, Vol. 21 (1966), pp. 133-134.

Intersection of A001567 and A036259.
A367231 is a subsequence.
Cf. A002326, A014663, A306413, A367229.

Select[2*Range[10^6] + 1, PowerMod[2, # - 1, #] == 1 && CompositeQ[#] && OddQ[MultiplicativeOrder[2, #]] &]

is(n) = n > 1 && n % 2 && Mod(2, n)^(n-1) == 1 && !isprime(n) && znorder(Mod(2, n)) % 2;

A074203 Odd numbers k such that the number of 1's in the binary representation of k divides 2^k-1.

Original entry on oeis.org

1, 351, 375, 381, 471, 477, 501, 687, 699, 747, 855, 861, 885, 939, 981, 1119, 1143, 1149, 1239, 1245, 1269, 1311, 1335, 1341, 1359, 1371, 1383, 1389, 1395, 1401, 1431, 1437, 1461, 1479, 1485, 1491, 1497, 1509, 1521, 1623, 1629, 1653, 1707, 1749, 1815

Offset: 1

Benoit Cloitre, Sep 17 2002

Except for 1, terms seem always divisible by 3.
From Robert Israel, Jan 14 2019: (Start)
An odd number k is in the sequence if and only if A000120(k) is in A036259 and k is divisible by A007733(A000120(k)).  In particular, there are infinitely many of these for every member of A036259 except 1.
Thus a(2) to a(28842) have A000120(k)=7 and are divisible by 3, but a(28843) = 12582911 has A000120(12582911) = 23 and is divisible by A007733(23) = 11 but not by 3. (End)

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000120, A007733, A036259, A074202.

filter:= n -> 2 &^ n - 1 mod convert(convert(n,base,2),`+`) = 0:
select(filter, [seq(i,i=1..2000,2)]); # Robert Israel, Jan 13 2019

Join[{1}, Select[Range[3, 2000, 2], PowerMod[2, #, DigitCount[#, 2, 1]] == 1 &]] (* Amiram Eldar, Jun 08 2022 *)

isok(n) = (n % 2) && !((2^n-1) % hammingweight(n)); \\ Michel Marcus, Nov 29 2013

A367231 Carmichael numbers k such that the multiplicative order of 2 modulo k is odd.

Original entry on oeis.org

15841, 52633, 5049001, 68154001, 104852881, 238244041, 382536001, 3215031751, 3863326897, 7211236033, 8214723001, 15462960481, 22008493921, 23000028481, 29392867201, 31708772257, 41217865921, 53125756201, 60518537641, 74190097801, 77874636001, 83828294551, 103387371361

Offset: 1

Amiram Eldar, Nov 11 2023

nonn

These Carmichael numbers seem to be relatively rare: among the 4279356 Carmichael numbers below 2^64 only 3097 are terms of this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (calculated using data from Claude Goutier)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Index entries for sequences related to Carmichael numbers.

Intersection of A002997 and A036259.
Subsequence of A367230.
Cf. A002326, A163956.

Select[2*Range[3*10^6] + 1, Mod[#, CarmichaelLambda[#]] == 1 && CompositeQ[#] && OddQ[MultiplicativeOrder[2, #]] &]

is(n) = n > 1 && n % 2 && !isprime(n) && n % lcm(znstar(n)[2]) == 1 && znorder(Mod(2, n)) % 2;

A303449 Denominator of (2n+1)/(2^(2n+1)-1).

Original entry on oeis.org

1, 7, 31, 127, 511, 2047, 8191, 32767, 131071, 524287, 299593, 8388607, 33554431, 134217727, 536870911, 2147483647, 8589934591, 34359738367, 137438953471, 549755813887, 2199023255551, 8796093022207, 35184372088831, 140737488355327, 562949953421311, 2251799813685247

Offset: 0

Altug Alkan, Apr 24 2018

If A160145(n) = 0, then a(n) = A083420(n).

Least values of k such that a(k) = A083420(k)/A036259(n) are 0, 10, 126, 77, 540, 73, 1242, 328, 1540, 489 for 1 <= n <= 10.

Cf. A005408, A036259, A083420, A160144 (numerators), A160145.

seq(denom((2*n+1)/(2^(2*n+1)-1)), n=0..25);

a(n) = denominator((2*n+1)/(2^(2*n+1)-1));

forstep(k=1, 1e2, 2, print1(denominator(k/(2^k-1)), ", "));

A348062 Primes p such that the length of the (eventual) period of the sequence {2^(2^k) mod p: k >= 0} is odd.

Original entry on oeis.org

2, 3, 5, 17, 29, 43, 47, 113, 127, 179, 197, 257, 277, 283, 293, 317, 383, 439, 449, 467, 479, 509, 569, 641, 659, 719, 797, 863, 1013, 1069, 1289, 1373, 1399, 1427, 1439, 1487, 1579, 1627, 1657, 1753, 1823, 1913, 1933, 1949, 2063, 2203, 2207, 2213, 2273, 2339, 2351

Offset: 1

Arkadiusz Wesolowski, Sep 26 2021

nonn

Of these numbers only 3 and 5 are elite primes (A102742). (Aigner)

Every prime of the form A036259(n)*2^m + 1, with m, n >= 1, is in this sequence.

Alexander Aigner, Über Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind, Monatsh. Math., Vol. 101 (1986), pp. 85-93; alternative link.

Supersequence of A023394.

Cf. A102742 (elite primes), A256607.

L=List([2]); forprime(p=3, 2351, z=znorder(Mod(2, p)); if(znorder(Mod(2, z/2^valuation(z, 2)))%2, listput(L, p))); Vec(L)

A349678 Primes p such that the multiplicative order of 2 modulo k is odd, where k is the largest odd divisor of p - 1.

Original entry on oeis.org

2, 3, 5, 17, 29, 47, 113, 179, 197, 257, 293, 317, 383, 449, 467, 479, 509, 569, 659, 719, 797, 863, 1289, 1373, 1427, 1439, 1487, 1823, 1913, 1949, 2063, 2207, 2213, 2273, 2339, 2417, 2447, 2579, 2633, 2879, 2909, 3023, 3119, 3137, 3167, 3347, 3359, 3449, 3557

Offset: 1

Arkadiusz Wesolowski, Nov 24 2021

nonn

Robert Israel, Table of n, a(n) for n = 1..10000

Subsequence of A348062.

Cf. A036259.

filter:= proc(p) local k;
  if not isprime(p) then return false fi;
  k:= (p-1)/2^padic:-ordp(p-1,2);
  numtheory:-order(2,k)::odd
end proc:
select(filter, [2,seq(i,i=3..10000,2)]); # Robert Israel, Feb 02 2025

Select[Range[3600], PrimeQ[#] && OddQ[MultiplicativeOrder[2, (# - 1)/2^IntegerExponent[# - 1, 2]]] &] (* Amiram Eldar, Nov 26 2021 *)

isok(p) = isprime(p) && znorder(Mod(2, (p-1)/2^valuation(p-1,2)))%2;

A306833 a(1) = 3; a(n+1) is the smallest k > a(n) such that 2^(k-1) == 1 (mod a(n)).

Original entry on oeis.org

3, 5, 9, 13, 25, 41, 61, 121, 221, 241, 265, 313, 469, 529, 760

Offset: 1

Thomas Ordowski, Mar 12 2019

This sequence is finite, the last term a(15) = 760 is even.
Conjecture: for any initial term a(1), this recursion gives a finite sequence (ends with an even term).
Theorem: for odd a(n), a(n+1) is even if and only if ord_{a(n)}(2) is odd and (a(n) mod ord_{a(n)}(2)) is odd.
The set of penultimate terms of the sequences is {A036259} \ {A036260}.

Cf. A002326, A036259, A036260.

lista(nn) = {a = 3; print1(a, ", "); for (n=2, nn, k = a+1; while (Mod(2, a)^(k-1) != 1, k++); a = k; print1(a, ", "); if (!(a%2), break););} \\ Michel Marcus, Mar 24 2019

cp's OEIS Frontend

A053006 Numbers m for which there exist d(1),...,d(m), each in {0,1}, such that Sum_{i=1..m-k} d(i)*d(i+k) is odd for all k=0,...,m-1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A296243 Numbers k such that the multiplicative order of 2 modulo k is even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A036260 Numbers k > 1 such that k mod ord2(k) is even, where ord2(k) is the order of 2 mod k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A367230 Base-2 Fermat pseudoprimes k such that the multiplicative order of 2 modulo k is odd.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A074203 Odd numbers k such that the number of 1's in the binary representation of k divides 2^k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A367231 Carmichael numbers k such that the multiplicative order of 2 modulo k is odd.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A303449 Denominator of (2*n+1)/(2^(2*n+1)-1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

PARI

A348062 Primes p such that the length of the (eventual) period of the sequence {2^(2^k) mod p: k >= 0} is odd.

Views

Author

A303449 Denominator of (2n+1)/(2^(2n+1)-1).