A072451 -id:A072451 - cp's OEIS frontend

A037225 a(n) = phi(2n+1).

1, 2, 4, 6, 6, 10, 12, 8, 16, 18, 12, 22, 20, 18, 28, 30, 20, 24, 36, 24, 40, 42, 24, 46, 42, 32, 52, 40, 36, 58, 60, 36, 48, 66, 44, 70, 72, 40, 60, 78, 54, 82, 64, 56, 88, 72, 60, 72, 96, 60, 100, 102, 48, 106, 108, 72, 112, 88, 72, 96, 110, 80, 100, 126, 84, 130

Offset: 0

N. J. A. Sloane

Bisection of A000010 (cf. A062570).
From Alain Rocchelli, Jun 28 2023: (Start)
If 2*n+1 has r distinct odd prime factors, 2^r divides a(n).
Conjectures:
1) For any composite integer 2*n+1, a(n) doesn't divide 2*n.
2) For all n, a(n) is never equal to n. (End)

T. D. Noe, Table of n, a(n) for n = 0..10000
John Brillhart, J. S. Lomont, and Patrick Morton, Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math. 288 (1976), 37-65; see Table 2; MR0498479 (58 #16589). - From _N. J. A. Sloane_, Jun 06 2012
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53 (in Russian).
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Problems of Information. Transmission, 43 (2007), 199-212 (translation from Russian).
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).
Wikipedia, Lehmer's totient problem.

Cf. A000010, A062570, A072451, A217739.

[EulerPhi(2*n+1): n in [0..70]]; // Vincenzo Librandi, Jul 16 2019

Table[EulerPhi[2 n + 1], {n, 0, 80}] (* Vincenzo Librandi, Jul 16 2019 *)

a(n) = eulerphi(2*n+1) \\ Amiram Eldar, Nov 17 2022

Sum_{k=0..n} a(k) ~ c * n^2, where c = 8/Pi^2 = 0.810569... (A217739). - Amiram Eldar, Nov 17 2022
a(n) = 2*n iff 2*n+1 is prime, see A005097. - Alain Rocchelli, Jun 22 2023
From Peter Bala, Feb 01 2024: (Start)
Odd bisection of A000010.
a(n) = 2*A072451(n) for n >= 1.
G.f.: Sum_{n >= 1} phi(2*n+1)*x^(2*n+1) = Sum_{n >= 1} moebius(n)*x^(2*n-1)*(1 + x^(4*n-2))/(1 - x^(4*n-2))^2 = x + 2*x^3 + 4*x^5 + 6*x^7 + 6*x^9 + .... (End)

A349136 Möbius transform of Kimberling's paraphrases, A003602.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 3, 0, 3, 0, 5, 0, 6, 0, 4, 0, 8, 0, 9, 0, 6, 0, 11, 0, 10, 0, 9, 0, 14, 0, 15, 0, 10, 0, 12, 0, 18, 0, 12, 0, 20, 0, 21, 0, 12, 0, 23, 0, 21, 0, 16, 0, 26, 0, 20, 0, 18, 0, 29, 0, 30, 0, 18, 0, 24, 0, 33, 0, 22, 0, 35, 0, 36, 0, 20, 0, 30, 0, 39, 0, 27, 0, 41, 0, 32, 0, 28, 0, 44, 0, 36, 0, 30, 0, 36

Offset: 1

Antti Karttunen, Nov 13 2021

nonn

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

Agrees with A055034 on odd arguments.
Cf. A000010, A003602, A008683, A349134.
Cf. A000004, A072451 (even and odd bisection).
Cf. also A347233, A349127, A349137.

with(numtheory): a:=proc(n) if n=1 then 1; elif n mod 2 = 0 then 0; else phi(n)/2; fi: end proc: seq(a(n), n=1..60); # Ridouane Oudra, Jul 13 2023

k[n_] := (n/2^IntegerExponent[n, 2] + 1)/2; a[n_] := DivisorSum[n, MoebiusMu[#] * k[n/#] &]; Array[a, 100] (* Amiram Eldar, Nov 13 2021 *)

A349136(n) = if(1==n,1, if(n%2, eulerphi(n)/2, 0));

A003602(n) = (1+(n>>valuation(n,2)))/2;
A349136(n) = sumdiv(n,d,moebius(d)*A003602(n/d));

from sympy import totient
def A349136(n): return totient(n)+1>>1 if n&1 else 0 # Chai Wah Wu, Nov 24 2023

a(n) = Sum_{d|n} A008683(d) * A003602(n/d).
a(1) = 1, a(n) = A000010(n)/2 for odd n > 1, a(n) = 0 for even n.
For all n >= 1, a(2*n-1) = A055034(2*n-1) = A072451(n).
a(n) = phi(n) - (1/2)*phi(2n), for n>1. - Ridouane Oudra, Jul 13 2023
Sum_{k=1..n} a(k) ~ (1/Pi^2)*n^2. - Amiram Eldar, Jul 15 2023

A216066 a(n) = card {cos((2^k)Pi/(2n-1)): k in N}.

Original entry on oeis.org

1, 1, 2, 3, 3, 5, 6, 4, 4, 9, 6, 11, 10, 9, 14, 5, 5, 12, 18, 12, 10, 7, 12, 23, 21, 8, 26, 20, 9, 29, 30, 6, 6, 33, 22, 35, 9, 20, 30, 39, 27, 41, 8, 28, 11, 12, 10, 36, 24, 15, 50, 51, 12, 53, 18, 36, 14, 44, 12, 24, 55, 20, 50, 7, 7, 65, 18, 36, 34, 69, 46

Offset: 1

Roman Witula, Sep 01 2012

nonn

Essentially the same as A003558: a(n) is equal to the minimal value r in N for which either 2^r is congruent to 1 modulo 2*n-1 or 2^r is congruent to -1 modulo 2*n-1.
In view of Sharkovsky's Theorem numbers a(n) exert an essential influence on the chaotic nature (in the sense of Li and Yorke) of polynomials, for which the set {cos((2^k)*Pi/(2*n-1)): k in N} is a periodic cycle. For example from a(4) = 3 it follows (see Witula-Slota reference) that the set {c(1;7), c(2;7), c(4;7)}, where c(j;7) := cos(2*Pi*j/7), is a 3-element orbit of the polynomial p(x) = -x^3 + 2*x - 1 = -(x - c(1;9))*(x - c(2;9))*(x - c(4;9)), where c(j;9) := cos(2*Pi*j/9). "Period 3 implies chaos" of p(x) in the sense of Li and Yorke. Moreover from the Sharkovsky Theorem p(x) possesses cycle orbits of any positive lengths.
We note that A072451(n) is divisible by a(n) for every n in N (see Corollary 5.8 a) in Witula-Slota's paper - "whenever l(n)..." could be replaced by "whenever n..." in this Corollary). We have a(n) = A072451(n) for every n=1,...,20 except 9, 16 and 17 (a(9)=4, a(16)=a(17)=5, A072451(9)=8, A072451(16)=15 and A072451(17)=10).
The following fact (strongly than previously one) is also true: the value of the Carmichael lambda function for the argument 2*n-1, i.e., A002322(2*n-1) is divisible by a(n) for every n in N.
I want to formulate some problem: for which k in N there is a subsequence k,k in the sequence a(n)? We note that for k = 1,3,...,7 the answer is positive. Moreover, I am interesting for which k in N the equation a(n) = k has the infinite set of solutions n in N?
I observe that also A065457(n) is divisible by a(n) for every n in N and A002322(2*n+1) is divisible by A065457(n+1) for every n in N - but I don't know why these relations hold true. - Roman Witula, Sep 10 2012
If you write n letters in a line, for example n=5, abcde, and then put the last after the first, the second last after the second and so on, you will get aebdc.  After this, you can apply the same transformation to the new string. Doing this transformation a(n) times will lead you eventually back to the original string; see the second PARI program. This idea is from Wolfgang Tomášek. - Robert Pfister, Sep 12 2013

			We have a(2)=1, a(3)=2, a(4)=3 and a(12)=11, a(11)=10, a(10)=9, and a(45)=11, a(46)=12, a(47)=10. Does exist some another k,l in N for which a(k)=p(l), a(k+1)=p(l+1), and a(k+2)=p(l+2), where p is a permutation on {l,l+1,l+2}?

Joerg Arndt, Table of n, a(n) for n = 1..1000
R. Witula and D. Slota, Fixed and periodic points of polynomials generated by minimal polynomials of 2cos(2Pi/n), International J. Bifurcation and Chaos, 19 (9) (2009), 3005.

A003558 is essentially the same sequence except for the offset.

Cf. A072451.

Suborder[k_, n_] := If[n > 1 && GCD[k, n] == 1, Min[MultiplicativeOrder[k, n, {-1, 1}]], 0];
a[n_] := If[n == 0, 1, Suborder[2, 2 n + 1]];
a /@ Range[0, 100] (* Jean-François Alcover, Mar 21 2020, after T. D. Noe in A003558 *)

a(n) = {
    my( g=Mod(2,2*n-1), f=g );
    for (r=1, 2*n+2,
        if ( f == +1, return(r) );
        if ( f == -1, return(r) );
        f *= g;
    );
}
/* Joerg Arndt, Sep 03 2012 */

/* computation by the comment from Robert Pfister: */
a(n) = {
    my( g = vectorsmall(n), e=vectorsmall(n,k,k), t );
    my( ct = 1 );
    \\ set g[] to the zip-permutation:
    forstep ( k=1, n, 2, g[k] = k\2 + 1);
    forstep ( k=2, n, 2, g[k] = n - k\2 + 1);
    t = g;
    while ( t != e,  \\ until we hit identity
        ct += 1;
        t *= g;  \\ t == g^ct
    );
    return( ct );
}
/* Joerg Arndt, Sep 12 2013 */

For n >= 2, a(n) = A003558(n-1).

A072455 Number of totients in the reduced residue system of 2n-1.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 7, 4, 8, 9, 7, 11, 10, 8, 13, 14, 9, 11, 16, 10, 17, 18, 9, 20, 19, 13, 22, 17, 15, 25, 26, 14, 21, 28, 16, 29, 30, 14, 23, 31, 19, 33, 27, 19, 35, 28, 22, 29, 37, 19, 38, 39, 16, 41, 42, 26, 44, 33, 26, 38, 41, 27, 36, 47, 29, 49, 43, 22, 51, 52, 32, 43, 40, 27

Offset: 1

Labos Elemer, Jun 19 2002

nonn

			For n=31: reduced residue system(31) = {1,...,30} with 15 odd and 15 even numbers. From the odd terms only the term 1 is totient, while from the 15 even terms, 2 terms, {14,26}, are nontotients, so 13 terms are totients. All totients count 1 + 13 = 14, thus a((31+1)/2) = a(16) = 14.

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

Cf. A000010, A002202, A005277, A037225, A072451, A072454.

a(n) = {my(m = 2*n-1); sum(k = 1, m, gcd(m, k) == 1 && istotient(k));} \\ Amiram Eldar, Nov 07 2024

a(n) = phi(2*n-1) - A072454(n). [Corrected by Sean A. Irvine, Oct 04 2024]

A072106 The number of nontotients (even and odd) in the reduced residue system of n.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 3, 2, 3, 4, 3, 5, 5, 4, 7, 8, 5, 9, 7, 5, 9, 11, 7, 10, 11, 10, 11, 15, 7, 16, 15, 11, 15, 13, 11, 20, 17, 14, 15, 23, 11, 24, 19, 15, 21, 26, 15, 23, 19, 19, 23, 30, 17, 23, 23, 21, 27, 33, 15, 34, 29, 22, 31, 27, 19, 38, 31, 28, 23, 41, 23, 42, 35, 26, 35, 37

Offset: 1

Labos Elemer, Jun 19 2002

nonn

			For n=113: the reduced residue system consists of 112 numbers: Card[OddNonTotients(113)] = 56 - 1, EvenNonTotients = {14,26,34,38,50,62,68,74,76,86,90,94,98}, i.e., 13 terms, therefore a(113) = 56 - 1 + 13 = 68.

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

Cf. A000010, A002202, A005277, A037225, A072451, A072455.

a(n) = sum(k = 1, n, gcd(n, k) == 1 && !istotient(k)); \\ Amiram Eldar, Nov 07 2024

A072454 Number of nontotients in the reduced residue system of 2n-1.

Original entry on oeis.org

0, 0, 1, 2, 2, 4, 5, 4, 8, 9, 5, 11, 10, 10, 15, 16, 11, 13, 20, 14, 23, 24, 15, 26, 23, 19, 30, 23, 21, 33, 34, 22, 27, 38, 28, 41, 42, 26, 37, 47, 35, 49, 37, 37, 53, 44, 38, 43, 59, 41, 62, 63, 32, 65, 66, 46, 68, 55, 46, 58, 69, 53, 64, 79, 55, 81, 65, 50, 85, 86, 60, 77, 72

Offset: 1

Labos Elemer, Jun 19 2002

nonn

			For n=105: phi(105) = 48 with 24 odd, 24 even terms in the reduced residue system, of which 9 even terms and (all but 1) odd term is nontotient: a((105+1)/2) = a(53) = 24-1+9 = 32.
For n=21: reduced residue system(21) = Union({1,5,11,13,17,19}, {2,4,8,16,20}) includes 6 odd and 5 even numbers. No even nontotients terms in the reduced residue system(21), so 6-1 = 5 odd terms give all nontotients, so a((21+1)/2) = a(11) = 5.

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

Cf. A000010, A002202, A005277, A037225, A072451, A072455.

Bisection of A072106.

a(n) = {my(m = 2*n-1); sum(k = 1, m, gcd(m, k) == 1 && !istotient(k));} \\ Amiram Eldar, Nov 07 2024

a(n) = A072106(2*n-1). - Amiram Eldar, Nov 07 2024

A126611 Sum x+y of generator pairs (x, y) {x and y coprime and not both odd} of primitive Pythagorean triangles, sorted.

Original entry on oeis.org

3, 5, 5, 7, 7, 7, 9, 9, 9, 11, 11, 11, 11, 11, 13, 13, 13, 13, 13, 13, 15, 15, 15, 15, 17, 17, 17, 17, 17, 17, 17, 17, 19, 19, 19, 19, 19, 19, 19, 19, 19, 21, 21, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 27, 27, 27, 27

Offset: 1

Lekraj Beedassy, Feb 07 2007

nonn

Also, the square root of the sum of even leg and hypotenuse of primitive Pythagorean triangles, sorted.

Cf. A094192, A094193.

2n-1 appears A072451(n) times.

A349339 Odd bisection of the Möbius transform of A126760.

Original entry on oeis.org

1, 0, 1, 2, 0, 3, 4, 0, 5, 6, 0, 7, 7, 0, 9, 10, 0, 8, 12, 0, 13, 14, 0, 15, 14, 0, 17, 14, 0, 19, 20, 0, 16, 22, 0, 23, 24, 0, 20, 26, 0, 27, 22, 0, 29, 24, 0, 24, 32, 0, 33, 34, 0, 35, 36, 0, 37, 30, 0, 32, 37, 0, 33, 42, 0, 43, 36, 0, 45, 46, 0, 40, 38, 0, 49, 50, 0, 40, 52, 0, 44, 54, 0, 55, 52, 0, 57, 40, 0, 59

Offset: 1

Antti Karttunen, Nov 16 2021

nonn

Cf. A126760, A347233.

Cf. also A072451 (the odd bisection of the Möbius transform of A003602).

A126760(n) = {n&&n\=3^valuation(n, 3)<A126760
A347233(n) = sumdiv(n,d,moebius(n/d)*A126760(d));
A349339(n) = A347233(n+n-1);

a(n) = A347233(2*n-1).

A378521 Möbius transform of A048673.

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 5, 9, 10, 6, 6, 12, 8, 10, 12, 27, 9, 20, 11, 18, 20, 12, 14, 36, 21, 16, 50, 30, 15, 24, 18, 81, 24, 18, 30, 60, 20, 22, 32, 54, 21, 40, 23, 36, 60, 28, 26, 108, 55, 42, 36, 48, 29, 100, 36, 90, 44, 30, 30, 72, 33, 36, 100, 243, 48, 48, 35, 54, 56, 60, 36, 180, 39, 40, 84, 66, 60, 64, 41, 162, 250

Offset: 1

Antti Karttunen, Nov 30 2024

nonn

Cf. A000010, A003961, A003972, A008683, A048673, A055034, A072451, A349136.

A048673(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); (factorback(f)+1)/2; };
A378521(n) = sumdiv(n,d,moebius(n/d)*A048673(d));

A003961(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A378521(n) = if(1==n,n,eulerphi(A003961(n))/2);

a(n) = Sum_{d|n} A008683(n/d)*A048673(d).
a(n) = A072451(A048673(n)).
a(n) = A055034(A003961(n)) = A349136(A003961(n)).
For n > 1, a(n) = A003972(n)/2 = A000010(A003961(n))/2.

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2n - 1 by Brändli and Beyne, called mod(2*n - 1).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 1, 2, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2, 4, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 4, 5, 8, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 1, 2, 4, 5, 7, 8, 10, 11, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Offset: 1

Wolfdieter Lang, Jun 27 2020

The length of row n is A072451(n) = A055034(2*n-1), for n >= 1.
See the Brändli-Beyne link, and A333856 for the definition and some examples of this mod* system.
This reduced residue system mod* (2*n - 1) will be called RRS*(2*n - 1).
Compare this table with the one for the reduced residue system modulo 2*n - 1 (called RRS(2*n - 1) = A038566(2*n - 1), but with A038566(1) = 0). For n >= 2 RRS*(2*n-1) consists of the first half of the entries of RRS(2*n - 1).
The modular arithmetic is multiplicative but not additive for mod*. See A333856 for examples.

			The irregular triangle T(n, k) begins (b = 2*n - 1):
n    b \k  1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 ...
---------------------------------------------------------------
1    1:    0
2    3:    1
3    5:    1 2
4    7:    1 2 3
5    9:    1 2 4
6   11:    1 2 3 4 5
7   13:    1 2 3 4 5  6
8   15:    1 2 4 7
9   17:    1 2 3 4 5  6  7  8
10  19:    1 2 3 4 5  6  7  8  9
11  21:    1 2 4 5 8 10
12  23:    1 2 3 4 5  6  7  8  9 10 11
13  25:    1 2 3 4 6  7  8  9 11 12
14  27:    1 2 4 5 7  8 10 11 13
15  29:    1 2 3 4 5  6  7  8  9 10 11 12 13 14
16  31:    1 2 3 4 5  6  7  8  9 10 11 12 13 14 15
17  33:    1 2 4 5 7  8 10 13 14 16
18  35:    1 2 3 4 6  8  9 11 12 13 16 17
19  37:    1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18
20  39:    1 2 4 5 7  8 10 11 14 16 17 19
...
-----------------------------------------------------------
For n = 5 (b = 9) see the example in A333856.

Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.

Cf. A055034, A072451, A038566, A333856.

Array[Function[{m, b}, Select[Range[1, m], GCD[#, b] == 1 &] /. {} -> {0}] @@ {# - 1, 2 # - 1} &, 16] // Flatten (* Michael De Vlieger, Jun 27 2020 *)

T(1, 1) = 0, T(n, k) = A038566(2*n - 1, k) for k = 1, 2, ..., A072451(n), for n >= 2.

cp's OEIS Frontend

A037225 a(n) = phi(2n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A349136 Möbius transform of Kimberling's paraphrases, A003602.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A216066 a(n) = card {cos((2^k)*Pi/(2*n-1)): k in N}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A072455 Number of totients in the reduced residue system of 2n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A072106 The number of nontotients (even and odd) in the reduced residue system of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A072454 Number of nontotients in the reduced residue system of 2n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A126611 Sum x+y of generator pairs (x, y) {x and y coprime and not both odd} of primitive Pythagorean triangles, sorted.

Views

Author

Keywords

Comments

Crossrefs

Formula

A349339 Odd bisection of the Möbius transform of A126760.

Views

Author

Keywords

Crossrefs

A216066 a(n) = card {cos((2^k)Pi/(2n-1)): k in N}.

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2n - 1 by Brändli and Beyne, called mod(2*n - 1).