A002326 -id:A002326 - cp's OEIS frontend

A179383 a(n) = 2*k(n)-1 where k(n) is the sequence of positions of records in A179382.

1, 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, 709, 757

Offset: 1

Vladimir Shevelev, Jul 12 2010

nonn

Records in A179382(k(n)) = 1, 2, 3, 5, 6, 9, 10, 14, 18, 26, 29, ....
are located at k(n) = 1, 3, 5, 6, 7, 10, 13, 15, 19, 27, 30, 31,..
The current sequence is a simple transformation of this k(n) sequence.
Question: Are there any terms in the sequence with two or more distinct prime divisors?
Some very plausible conjectures: 1) The sequence consists of primes and squares of primes; 2) The set of squares is finite; 3) A prime p>=5 is in the sequence iff it has primitive root 2 (A001122) ; 4) There exists l such that, for n>l, A179383(n) =A139099(n+l) . [From Vladimir Shevelev , Jul 14 2010]

Peter J. C. Moses, Table of n, a(n) for n = 1..8500

Cf. A139099, A167791, A002326, A179382

Definition rephrased and sequence extended by R. J. Mathar, Jul 13 2010

I made a change to Conjecture 4). - Vladimir Shevelev, Jul 18 2010

A179680 The number of exponents >1 in a recursive reduction of 2n-1 until reaching an odd part equal to 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 3, 1, 1, 5, 1, 3, 5, 5, 7, 1, 1, 3, 9, 3, 3, 3, 3, 6, 5, 2, 13, 5, 3, 15, 15, 1, 1, 17, 5, 9, 1, 5, 7, 10, 13, 21, 1, 7, 2, 3, 2, 9, 11, 9, 25, 13, 2, 27, 9, 9, 5, 11, 2, 6, 27, 5, 25, 1, 1, 33, 3, 9, 15, 35, 11, 15, 3, 11, 37, 3, 6, 5, 13, 13

Offset: 1

Vladimir Shevelev, Jul 24 2010

nonn

Let N = 2n-1. Then consider the following algorithm of updating pairs (v,m) indicating highest exponent of 2 (2-adic valuation) and odd part: Initialize at step 1 by v(1) = A007814(N+1) and m(1) = A000265(N+1). Iterate over steps i>=2: v(i) = A007814(N+m(i-1)), m(i) = A000265(N+m(i-1)) using the previous odd part m(i-1) until some m(k) = 1. a(n) is defined as the count of the v(i) which are larger than 1.
This is an algorithm to compute A002326 because the sum v(1)+v(2)+ ... +v(k) of the exponents is A002326(n-1).
A179382(n) = 1 + the number of iterations taken by the algorithm when starting from N = 2n-1. - Antti Karttunen, Oct 02 2017

			For n = 9, 2*n-1 = 17, we have v_1 = v_2 = v_3 = 1, v_4 = 5. Thus a(9) = 1.
For n = 10, 2*n-1 = 19, we have v_1 = 2, v_2 = 3, v_3 = v_4 = v_5 = 1, v_6 = v_7 = 2, v_8 = 1, v_9 = 5. Thus a(10) = 5.

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A179676, A179460, A007814, A002326, A179382, A292239, A292265, A292266.

A179680 := proc(n) local l,m,a ,N ; N := 2*n-1 ; a := 0 ; l := A007814(N+1) ; m := A000265(N+1) ; if l > 1 then a := a+1 ; end if; while m <> 1 do l := A007814(N+m) ; if l > 1 then a := a+1 ; end if; m := A000265(N+m) ; end do: a ; end proc:
seq(A179680(n),n=1..80) ; # R. J. Mathar, Apr 05 2011

a7814[n_] := IntegerExponent[n, 2];
a265[n_] := n/2^IntegerExponent[n, 2];
a[n_] := Module[{l, m, k, nn}, nn = 2n-1; k = 0; l = a7814[nn+1]; m = a265[nn+1]; If[l>1, k++]; While[m != 1, l = a7814[nn+m]; If[l>1, k++]; m = a265[nn+m]]; k];
Array[a, 80] (* Jean-François Alcover, Jul 30 2018, after R. J. Mathar *)

def A179680(n):
    s, m, N = 0, 1, 2*n - 1
    while True:
        k = N + m
        v = valuation(k, 2)
        if v > 1: s += 1
        m = k >> v
        if m == 1: break
    return s
print([A179680(n) for n in (1..80)]) # Peter Luschny, Oct 07 2017

(define (A179680 n) (let ((x (+ n n -1))) (let loop ((s (- 1 (A000035 n))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) s (loop (+ s (if (> (A007814 (+ x m)) 1) 1 0)) m)))))) ;; Antti Karttunen, Oct 02 2017

A256607 Eventual period of 2^(2^k) mod n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 2, 1, 1, 1, 2, 6, 1, 2, 4, 10, 1, 4, 2, 6, 2, 3, 1, 4, 1, 4, 1, 2, 2, 6, 6, 2, 1, 4, 2, 3, 4, 2, 10, 11, 1, 6, 4, 1, 2, 12, 6, 4, 2, 6, 3, 28, 1, 4, 4, 2, 1, 2, 4, 10, 1, 10, 2, 12, 2, 6, 6, 4, 6, 4, 2, 12, 1, 18, 4, 20, 2, 1, 3

Offset: 1

Ivan Neretin, Apr 04 2015

nonn

In other words, eventual period of 2 under the map x -> x^2 mod n.

a(n) is a divisor of A256608(n).

			For n=9 the map acts as follows: 2 -> 4 -> 7 -> 4 -> 7 and so on. This means the eventual period is 2, hence a(9)=2.

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A001146, A007733, A002326.
First differs from A256608 at n=43.
Column 2 of triangle in A279185.

a256607 = a007733 . fromIntegral . a007733
-- Reinhard Zumkeller, Apr 13 2015

a(n) = A007733(A007733(n)).

A270096 Smallest m such that 2^m == 2^n (mod n).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 4, 5, 2, 9, 4, 1, 2, 1, 5, 3, 2, 11, 6, 1, 2, 3, 4, 1, 6, 1, 4, 9, 2, 1, 4, 7, 10, 3, 4, 1, 18, 15, 5, 3, 2, 1, 4, 1, 2, 3, 6, 5, 6, 1, 4, 3, 10, 1, 6, 1, 2, 15, 4, 17, 6, 1, 4

Offset: 1

Thomas Ordowski, Mar 11 2016

nonn

a(n) = 1 iff n is a prime or a pseudoprime (odd or even) to base 2.
We have a(n) <= n - phi(n) and a(n) <= phi(n), so a(n) <= n/2.
From Robert Israel, Mar 11 2016: (Start)
If n is in A167791, then a(n) = A068494(n).
If n is odd, a(n) = n mod A002326((n-1)/2).
a(n) >= A007814(n).
a(p^k) = p^(k-1) for all k >= 1 and all odd primes p not in A001220.
Conjecture: a(n) <= n/3 for all n > 8. (End)

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

Cf. A000010, A001220, A002326, A007814, A051953, A068494, A167791.

Cf. A276976 (a generalization on all integer bases).

f:= proc(n) local d,b,t, m,c;
  d:= padic:-ordp(n,2);
  b:= n/2^d;
  t:= 2 &^ n mod n;
  m:= numtheory:-mlog(t,2,b,c);
  if m < d then m:= m + c*ceil((d-m)/c) fi;
  m
end proc:
f(1):= 0:
map(f, [$1..1000]; # Robert Israel, Mar 11 2016

Table[k = 0; While[PowerMod[2, n, n] != PowerMod[2, k, n], k++]; k, {n, 120}] (* Michael De Vlieger, Mar 15 2016 *)

a(n) = {my(m = 0); while (Mod(2, n)^m != 2^n, m++); m; } \\ Altug Alkan, Sep 23 2016

a(n) < n/2 for n > 4.
a(2^k) = k for all k >= 0.
a(2*p) = 2 for all primes p.

More terms from Michel Marcus, Mar 11 2016

A003573 Order of 4 mod 4n+1.

Original entry on oeis.org

1, 2, 3, 6, 4, 3, 10, 14, 5, 18, 10, 6, 21, 26, 9, 30, 6, 11, 9, 15, 27, 4, 11, 5, 24, 50, 6, 18, 14, 6, 55, 50, 7, 9, 34, 23, 14, 74, 12, 26, 33, 10, 78, 86, 29, 90, 18, 9, 48, 98, 33, 10, 45, 35, 15, 12, 30, 38, 29, 39, 12, 42, 41, 55, 8, 42, 26, 134, 6, 46, 35

Offset: 0

N. J. A. Sloane

nonn

Muniru A Asiru, Table of n, a(n) for n = 0..10000

Cf. A003574. First bisection of A053447.

Cf. A002326, A003571, A217469.

List([0..70],n->OrderMod(4,4*n+1)); # Muniru A Asiru, Feb 16 2019

a := n -> `if`(n=0, 1, numtheory:-order(4, 4*n+1)): seq(a(n), n = 0..68);

Table[MultiplicativeOrder[4, 4*n + 1], {n, 0, 70}] (* Arkadiusz Wesolowski, Nov 27 2012 *)

a(n) = znorder(Mod(4, 4*n+1)); \\ Michel Marcus, Feb 16 2019

def A003573(n):
    s, m, N = 0, 1, 4*n + 1
    while True:
        k = N + m
        v = valuation(k, 4)
        s += v
        m = k // 4^v
        if m == 1: break
    return s
print([A003573(n) for n in (0..70)]) # Peter Luschny, Oct 07 2017

a(n) = A053447(2*n) for n >= 0. - Jianing Song, Oct 03 2022

a(0) = 1 added by Peter Luschny, Oct 07 2017

A059907 a(n) = |{m : multiplicative order of n mod m = 2}|.

Original entry on oeis.org

0, 1, 2, 2, 5, 2, 6, 4, 6, 3, 12, 2, 10, 6, 8, 4, 13, 2, 18, 6, 10, 4, 16, 4, 12, 9, 12, 4, 26, 2, 20, 6, 8, 12, 20, 4, 15, 6, 16, 4, 32, 2, 24, 10, 10, 6, 20, 4, 26, 9, 18, 4, 26, 6, 32, 12, 12, 4, 28, 2, 20, 10, 12, 18, 25, 4, 24, 6, 26, 4, 52, 2, 18, 10, 12, 18, 26, 4, 40, 8, 14, 5, 28

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, GCD(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

			a(2) = |{3}| = 1, a(3) = |{4,8}| = 2, a(4) = |{5,15}| = 2, a(5) = |{3,6,8,12,24}| = 5, a(6) = |{7,35}| = 2, a(7) = |{4,8,12,16,24,48}| = 6,...

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A002329, A059908-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A055205, A048691, A048785, A347191.

Row n=2 of A212957. - Alois P. Heinz, Oct 24 2012

with(numtheory):f := n->tau(n^2-1)-tau(n-1):for n from 1 to 100 do printf(`%d,`,f(n)) od:

a[n_] := Subtract @@ DivisorSigma[0, {n^2-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^2-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^2-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A093106 Numbers k such that the k-th cyclotomic polynomial evaluated at 2 (=A019320(k)) is not coprime to k.

Original entry on oeis.org

6, 18, 20, 21, 54, 100, 110, 136, 147, 155, 156, 162, 253, 342, 486, 500, 602, 657, 812, 820, 889, 979, 1029, 1081, 1210, 1332, 1458, 2028, 2265, 2312, 2485, 2500, 2756, 3081, 3164, 3422, 3660, 3924, 4112, 4374, 4422, 4656, 4805, 5253, 5784, 5819, 6498

Offset: 1

Ralf Stephan, Mar 20 2004

nonn

Also, numbers k such that the Zsigmondy number Zs(k, 2, 1) differs from the k-th cyclotomic polynomial evaluated at 2, i.e., A064078(k) differs from A019320(k).

Numbers k > 0 such that A019320(k) is not congruent to 1 mod k. These numbers are of the form k = p^j * A002326((p-1)/2), where p is an odd prime and j > 0. Then A019320(k) mod k = gcd(A019320(k), k) = A019320(k) / A064078(k) = p. - Thomas Ordowski, Oct 07 2017

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..51350

Cf. A093107, A093108, A093109.

Select[Range[10000],GCD[#,Cyclotomic[#,2]]!=1 &] (* Emmanuel Vantieghem, Nov 13 2016 *)

isok(k) = gcd(polcyclo(k, 2), k) != 1; \\ Michel Marcus, Oct 07 2017

upto(K)=li=List();forprime(p=3,K*log(2)/log(K+1),r=znorder(Mod(2,p))*p;while(r<=K,listput(li,r);r*=p));Set(li) \\ Jeppe Stig Nielsen, Sep 10 2020

More terms from Vladeta Jovovic, Apr 03 2004
Definition corrected by Jerry Metzger, Nov 04 2009
Edited by Max Alekseyev, Oct 23 2017

A138193 Odd composite numbers n for which A137576((n-1)/2)-1 is divisible by phi(n).

Original entry on oeis.org

9, 15, 25, 27, 33, 39, 49, 55, 57, 63, 81, 87, 95, 111, 119, 121, 125, 135, 143, 153, 159, 161, 169, 175, 177, 183, 201, 207, 209, 225, 243, 249, 287, 289, 295, 297, 303, 319, 321, 329, 335, 343, 351, 361, 369, 375, 391, 393, 407, 415, 417, 423, 447, 489, 497

Offset: 1

Vladimir Shevelev, May 04 2008

nonn

If p is an odd prime then A137576((p-1)/2)=p. Therefore the composite numbers n may be considered as quasiprimes. In particular, if (m,n)=1 we have a natural generalization of the little Fermat theorem: m^(A137576((n-1)/ 2)-1)=1 mod n.

			a(1)=9: A137576(4)=13 and 13-1 is divisible by phi(9)=6.

Ray Chandler, Table of n, a(n) for n=1..1239

Cf. A137576, A002326, A006694.

A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1];
okQ[n_] := OddQ[n] && CompositeQ[n] && Divisible[A137576[(n - 1)/2] - 1, EulerPhi[n]];
Reap[For[k = 1, k < 500, k += 2, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* Jean-François Alcover, Jan 11 2019 *)

Extended by Ray Chandler, May 08 2008

A138217 Odd numbers n for which A137576((n-1)/2)-1 is a multiple of A000010(n).

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 53, 55, 57, 59, 61, 63, 67, 71, 73, 79, 81, 83, 87, 89, 95, 97, 101, 103, 107, 109, 111, 113, 119, 121, 125, 127, 131, 135, 137, 139, 143, 149, 151, 153, 157, 159, 161, 163, 167, 169, 173

Offset: 1

Vladimir Shevelev, May 05 2008

nonn

The sequence contains all odd primes. Indeed, if p is a prime then A137576((p-1)/2)-1=p-1=A000010(p).
Conjecture: the sequence contains infinitely many composite numbers.
The conjecture is true because of the sequence contains all powers of odd primes. Indeed, A137576((P^k-1)/2)-1=k*A000010(p^k). - Vladimir Shevelev, May 29 2008

Ray Chandler, Table of n, a(n) for n=1..3501

Cf. A137576, A000010, A002326, A006694.

A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1];
okQ[n_] := OddQ[n] && Divisible[A137576[(n - 1)/2] - 1, EulerPhi[n]];
Reap[For[k = 1, k < 200, k += 2, If[okQ[k], Sow[k]]]][[2, 1]] (* Jean-François Alcover, Jan 11 2019 *)

Extended by Ray Chandler, May 08 2008

A138227 Odd positive integers n for which A137576((n-1)/2)-1 is not a multiple of A000010(n).

Original entry on oeis.org

21, 35, 45, 51, 65, 69, 75, 77, 85, 91, 93, 99, 105, 115, 117, 123, 129, 133, 141, 145, 147, 155, 165, 171, 185, 187, 189, 195, 203, 205, 213, 215, 217, 219, 221, 231, 235, 237, 245, 247, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 291, 299, 301, 305

Offset: 1

Vladimir Shevelev, May 05 2008

nonn

All terms are composite numbers since if p is an odd prime then A137576((p-1)/2)-1=p-1=A000010(p).

Conjecture. This sequence is infinite.

Ray Chandler, Table of n, a(n) for n = 1..6500

Cf. A137576, A000010, A002326, A006694.

A137576[n_] := With[{t = MultiplicativeOrder[2, 2 n + 1]}, t*DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1]; Select[Range[1, 1000, 2], !Divisible[A137576[(# - 1)/2] - 1, EulerPhi[#]]&] (* Jean-François Alcover, Dec 07 2015 *)

is(n)=my(t); n%2 && (sumdiv(n,d,eulerphi(d)/(t=znorder(Mod(2, d))))*t-t)%eulerphi(n)>0 \\ Charles R Greathouse IV, Feb 20 2013

Extended by Ray Chandler, May 08 2008

cp's OEIS Frontend

A179383 a(n) = 2*k(n)-1 where k(n) is the sequence of positions of records in A179382.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A179680 The number of exponents >1 in a recursive reduction of 2n-1 until reaching an odd part equal to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Scheme

A256607 Eventual period of 2^(2^k) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Formula

A270096 Smallest m such that 2^m == 2^n (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003573 Order of 4 mod 4n+1.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Sage

Formula

Extensions

A059907 a(n) = |{m : multiplicative order of n mod m = 2}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A093106 Numbers k such that the k-th cyclotomic polynomial evaluated at 2 (=A019320(k)) is not coprime to k.

Views

Author

Keywords

Comments

Links

Crossrefs