A290731 -id:A290731 - cp's OEIS frontend

A290732 Number of distinct values of X(3X-1)/2 mod n.

1, 2, 3, 4, 3, 6, 4, 8, 9, 6, 6, 12, 7, 8, 9, 16, 9, 18, 10, 12, 12, 12, 12, 24, 11, 14, 27, 16, 15, 18, 16, 32, 18, 18, 12, 36, 19, 20, 21, 24, 21, 24, 22, 24, 27, 24, 24, 48, 22, 22, 27, 28, 27, 54, 18, 32, 30, 30, 30, 36

Offset: 1

N. J. A. Sloane, Aug 10 2017

			The values taken by (3*X^2-X)/2 mod n for small n are:
   1, [0]
   2, [0, 1]
   3, [0, 1, 2]
   4, [0, 1, 2, 3]
   5, [0, 1, 2]
   6, [0, 1, 2, 3, 4, 5]
   7, [0, 1, 2, 5]
   8, [0, 1, 2, 3, 4, 5, 6, 7]
   9, [0, 1, 2, 3, 4, 5, 6, 7, 8]
  10, [0, 1, 2, 5, 6, 7]
  11, [0, 1, 2, 4, 5, 7]
  12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..10000
Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], (24-August-2016). See Table 6.

Cf. A000224 (analog for X^2), A014113, A290729, A290730, A290731, A317623.

a:=[]; M:=80;
for n from 1 to M do
q1:={};
for i from 0 to 2*n-1 do q1:={op(q1), i*(3*i-1)/2 mod n}; od;
s1:=sort(convert(q1,list));
a:=[op(a),nops(s1)];
od:
a;

a[n_] := Table[PolynomialMod[X(3X-1)/2, n], {X, 0, 2*n-1}]// Union // Length;
Array[a, 60] (* Jean-François Alcover, Sep 01 2018 *)

a(n)={my(v=vector(n)); for(i=0, 2*n-1, v[i*(3*i-1)/2%n + 1]=1); vecsum(v)} \\ Andrew Howroyd, Oct 27 2018

a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); if(p<=3, p^e, 1 + p^(e+1)\(2*p+2)))} \\ Andrew Howroyd, Nov 03 2018

a(3^n) = 3^n. - Hugo Pfoertner, Aug 25 2018
a(n) = A317623(n) * A040001(n). - Andrew Howroyd, Oct 27 2018
Multiplicative with a(2^e) = 2^e, a(3^e) = 3^e, a(p^e) = 1 + floor( p^(e+1)/(2*p+2) ) for prime p >= 5. - Andrew Howroyd, Nov 03 2018

Even terms corrected by Andrew Howroyd, Nov 03 2018

A376202 Number of pairs 1 <= x <= y <= n-1 such that gcd(x,n) = gcd(y,n) = gcd(x+y,n) = 1 and 1/x + 1/y == 1/(x+y) mod n.

Original entry on oeis.org

0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 18, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 36, 0, 24, 0, 0, 0, 42, 0, 0, 0, 0, 0, 42, 0, 0, 0, 0, 0, 0, 0, 36, 0, 0, 0, 60, 0, 0, 0, 0, 0, 66, 0, 0, 0, 0, 0, 72, 0, 0, 0, 0, 0, 78, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 144, 0, 60, 0, 0, 0, 96, 0, 0, 0, 0, 0, 102, 0, 0

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

In general, 1/x + 1/y = 1/(x+y) is the wrong way to add fractions!
See A376203 for a(2*n-1)/2 and A376755 for a(6*n+1)/6.
From Robert Israel, Nov 06 2024: (Start)
If a(n) = 0 then a(m) = 0 whenever m is a multiple of n.
It appears that the primes p for which a(p) > 0 are A007645. (End)

			For n = 3 the a(3) = 2 solutions are (x,y) = (1,1) and (2,2).
For n = 7 the a(7) = 6 solutions are (x,y) = (1,2), (1,4), (2,4), (3,5), (3,6), (5,6).

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

Cf. A000086, A007645, A046530, A290731, A376203, A376755, A376756, A376757.

a:=[];
for n from 1 to 140 do
c:=0;
for y from 1 to n-1 do
for x from 1 to y do
if gcd(y,n) = 1 and gcd(x,n) = 1 and gcd(x+y,n) = 1  and (1/x + 1/y - 1/(x+y)) mod n = 0 then c:=c+1; fi;
od: # od x
od: # od y
a:=[op(a),c];
od: # od n
a;

from math import gcd
def A376202(n):
    c = 0
    for x in range(1,n):
        if gcd(x,n) == 1:
            for y in range(x,n):
                if gcd(y,n)==gcd(z:=x+y,n)==1 and not (w:=z**2-x*y)//gcd(w,x*y*z)%n:
                    c += 1
    return c # Chai Wah Wu, Oct 06 2024

A376203 a(n) = A376202(2*n-1)/2.

Original entry on oeis.org

0, 1, 0, 3, 0, 0, 6, 0, 0, 9, 6, 0, 0, 0, 0, 15, 0, 0, 18, 12, 0, 21, 0, 0, 21, 0, 0, 0, 18, 0, 30, 0, 0, 33, 0, 0, 36, 0, 0, 39, 0, 0, 0, 0, 0, 72, 30, 0, 48, 0, 0, 51, 0, 0, 54, 36, 0, 0, 0, 0, 0, 0, 0, 63, 42, 0, 108, 0, 0, 69

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..7814

Cf. A000086, A087786, A046530, A290731, A376202, A376755, A376756, A376757.

from math import gcd
def A376203(n):
    c, m = 0, (n<<1)-1
    for x in range(1,m):
        if gcd(x,m) == 1:
            for y in range(x,m):
                if gcd(y,m)==gcd(z:=x+y,m)==1 and not (w:=z**2-x*y)//gcd(w,x*y*z)%m:
                    c += 1
    return c>>1 # Chai Wah Wu, Oct 06 2024

A376755 a(n) = A376202(6*n+1)/6.

Original entry on oeis.org

1, 2, 3, 0, 5, 6, 7, 7, 0, 10, 11, 12, 13, 0, 24, 16, 17, 18, 0, 0, 21, 36, 23, 0, 25, 26, 27, 26, 0, 30, 0, 32, 33, 0, 35, 60, 37, 38, 0, 40, 72, 0, 72, 0, 45, 46, 47, 0, 0, 84, 51, 52, 0, 0, 55, 56, 49, 58, 0, 57, 61, 62, 63, 0, 0, 66, 120, 68, 0, 70, 120, 72

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..3470

Cf. A000086, A046530, A087786, A290731, A376202, A376203, A376756, A376757.

from math import gcd
def A376755(n):
    c, m = 0, 6*n|1
    for x in range(1,m):
        if gcd(x,m) == 1:
            for y in range(x,m):
                if gcd(y,m)==gcd(z:=x+y,m)==1 and not (w:=z**2-x*y)//gcd(w,x*y*z)%m:
                    c += 1
    return c//6 # Chai Wah Wu, Oct 06 2024

a(51)-a(72) from Chai Wah Wu, Oct 06 2024

A376756 Number of pairs 0 <= x <= y <= n-1 such that x^2 + x*y + y^2 == 0 (mod n).

Original entry on oeis.org

1, 1, 3, 3, 1, 3, 7, 3, 6, 1, 1, 9, 13, 7, 3, 10, 1, 6, 19, 3, 21, 1, 1, 9, 15, 13, 18, 27, 1, 3, 31, 10, 3, 1, 7, 21, 37, 19, 39, 3, 1, 21, 43, 3, 6, 1, 1, 30, 70, 15, 3, 51, 1, 18, 1, 27, 57, 1, 1, 9, 61, 31, 60, 36, 13, 3, 67, 3, 3, 7, 1, 21, 73, 37, 45, 75, 7, 39, 79, 10, 45, 1, 1, 81, 1, 43, 3, 3, 1, 6, 163, 3, 93, 1, 19, 30, 97

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000086, A046530, A087786, A290731, A376202, A376203, A376755, A376757.

def A376756(n):
    c = 0
    for x in range(n):
        z = x**2%n
        for y in range(x,n):
            if not (z+y*(x+y))%n:
                c += 1
    return c # Chai Wah Wu, Oct 06 2024

A376757 Number of pairs 0 <= x <= y <= n-1 such that x^3 == y^3 (mod n).

Original entry on oeis.org

1, 2, 3, 5, 5, 6, 13, 14, 18, 10, 11, 15, 25, 26, 15, 28, 17, 36, 37, 25, 39, 22, 23, 42, 35, 50, 81, 71, 29, 30, 61, 72, 33, 34, 65, 99, 73, 74, 75, 70, 41, 78, 85, 55, 90, 46, 47, 84, 112, 70, 51, 137, 53, 162, 55, 218, 111, 58, 59, 75, 121, 122, 288, 208, 125, 66, 133, 85, 69, 130, 71, 306, 145, 146, 105, 203, 143, 150, 157

Offset: 1

Tom Duff and N. J. A. Sloane, Oct 06 2024

nonn

A087786 includes pairs (x,y) with x>y (which are excluded from the present sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000086, A087786, A046530, A290731, A376202, A376203, A376755, A376756.

a(n) = sum(x=0, n-1, sum(y=x, n-1, Mod(x, n)^3 == Mod(y, n)^3)); \\ Michel Marcus, Oct 06 2024

from collections import Counter
def A376757(n): return sum(d*(d+1)>>1 for d in Counter(pow(x,3,n) for x in range(n)).values()) # Chai Wah Wu, Oct 06 2024

A290727 Analog of A085635, replacing "quadratic residue" (X^2) with "value of X^2+X".

Original entry on oeis.org

1, 2, 6, 10, 14, 18, 30, 42, 66, 70, 90, 126, 198, 210, 330, 390, 450, 630, 990, 1170, 1386, 1638, 2142, 2310, 2730, 3150, 4950, 5850, 6930, 8190, 10710, 11970, 12870, 16830, 18018, 23562, 26334, 27846, 30030, 34650

Offset: 1

N. J. A. Sloane, Aug 10 2017

nonn

Positions where R(k) = A290731(k)/k achieves a new minimum, i.e., R(k) < R(j), j = 0..k-1, R(0) = 2.

Hugo Pfoertner, Table of n, a(n) for n = 1..116
Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], 2016-2018. See Table 5.

Cf. A085635, A084848, A290728, A290731.

a290731[n_] := Product[{p, e} = pe; If[p == 2, 2^(e-1), 1+Quotient[p^(e+1), (2p+2)]], {pe, FactorInteger[n]}];
Reap[For[r = 2; k = 1, k <= 35000, k++, t = a290731[k]/k; If[tJean-François Alcover, Sep 03 2018, from PARI *)

a290731(n)={my(f=factor(n));prod(i=1,#f~,my([p,e]=f[i,]);if(p==2,2^(e-1),1+p^(e+1)\(2*p+2)))} \\ from Andrew Howroyd
r=2;for(k=1,40000,t=a290731(k)/k;if(tHugo Pfoertner, Aug 23 2018

More terms from Hugo Pfoertner, Aug 22 2018

Initial term added by Hugo Pfoertner, Aug 23 2018

A290728 Analog of A084848, replacing "quadratic residue" (X^2) with "value of X^2+X".

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 6, 8, 12, 12, 12, 16, 24, 24, 36, 42, 44, 48, 72, 84, 96, 112, 144, 144, 168, 176, 264, 308, 288, 336, 432, 480, 504, 648, 672, 864, 960, 1008, 1008, 1056, 1232, 1584, 1760, 1848, 2376, 2016, 2592

Offset: 1

N. J. A. Sloane, Aug 10 2017

nonn

Hugo Pfoertner, Table of n, a(n) for n = 1..116
Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], 2016-2018. See Table 5.

Cf. A085635, A084848, A290727, A290731.

a290731[n_] := Product[{p, e} = pe; If[p==2, 2^(e-1), 1 + Quotient[p^(e+1), (2p + 2)]], {pe, FactorInteger[n]}];
Reap[For[r = 2; k = 1, k <= 200000, k++, v = a290731[k]; t = v/k; If[t < r, r = t; Sow[v]]]][[2, 1]] (* Jean-François Alcover, Sep 13 2018, from PARI *)

a290731(n)={my(f=factor(n));prod(i=1,#f~,my([p,e]=f[i,]);if(p==2,2^(e-1),1+p^(e+1)\(2*p+2)))} \\ from Andrew Howroyd
r=2;for(k=1,200000,v=a290731(k);t=v/k;if(tHugo Pfoertner, Aug 23 2018

a(n) = A290731(A290727(n)) - Hugo Pfoertner, Aug 23 2018

More terms from Hugo Pfoertner, Aug 22 2018

Initial term added by Hugo Pfoertner, Aug 23 2018

A317623 Number of distinct values of X(3X-1) mod n.

Original entry on oeis.org

1, 1, 3, 2, 3, 3, 4, 4, 9, 3, 6, 6, 7, 4, 9, 8, 9, 9, 10, 6, 12, 6, 12, 12, 11, 7, 27, 8, 15, 9, 16, 16, 18, 9, 12, 18, 19, 10, 21, 12, 21, 12, 22, 12, 27, 12, 24, 24, 22, 11, 27, 14, 27, 27, 18, 16, 30, 15, 30, 18, 31, 16, 36, 32, 21, 18, 34, 18, 36, 12, 36

Offset: 1

Andrew Howroyd, Aug 01 2018

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

Cf. A000224, A290731, A290732.

f[2, e_] := 2^(e-1); f[3, e_] := 3^e; f[p_, e_] := 1 + Floor[p^(e+1)/(2*p+2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 13 2020 *)

a(n)={my(v=vector(n)); for(i=0, n-1, v[i*(3*i-1)%n + 1]=1); vecsum(v)}

a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); if(p<=3, if(p==2, 2^(e-1), 3^e), 1 + p^(e+1)\(2*p+2)))}

Multiplicative with a(2^e) = 2^(e-1), a(3^e) = 3^e, a(p^e) = 1 + floor( p^(e+1)/(2*p+2) ) for prime p >= 5.

A328701 Period in residues modulo n in iteration of x^2 + x + 1 starting at 0.

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 3, 4, 2, 1, 2, 2, 3, 3, 2, 8, 1, 2, 2, 2, 6, 2, 4, 4, 4, 3, 2, 6, 7, 2, 7, 16, 2, 1, 3, 2, 3, 2, 6, 4, 7, 6, 5, 2, 2, 4, 5, 8, 3, 4, 2, 6, 1, 2, 2, 12, 2, 7, 11, 2, 4, 7, 6, 32, 3, 2, 2, 2, 4, 3, 10, 4, 18, 3, 4, 2, 6, 6, 3, 8, 2, 7, 2, 6, 1, 5, 14, 4, 1, 2, 3

Offset: 1

Jianing Song, Oct 26 2019

nonn

a(n) is the period of {A002065 mod n}.
Let f(0) = 0, f(k+1) = (f(k)^2+f(k)+1) mod n, then a(n) is the smallest t such that f(i) = f(i+t) for all sufficiently large i.
Obviously a(n) <= A290731(n): f(1), f(2), ..., f(A290731(n)+1) are all of the form (s^2+s+1) mod n, so there must exists 1 <= i < j <= A290731(n)+1 such that f(i) = f(j), and a(n) <= j - i <= A290731(n). The equality seems to hold only for n = 3, 6 or n is a power of 2.

			In the following example, () denotes the cycles.
A002065(n) mod 4: 0, (1, 3), so a(4) = 2.
A002065(n) mod 7: 0, (1, 3, 6), so a(7) = 3.
A002065(n) mod 29: 0, (1, 3, 13, 9, 4, 21, 28), so a(29) = 7.
A002065(n) mod 61: (0, 1, 3, 13). {A002065(n) mod 61} enters into the cycle (0, 1, 3, 13) from the very beginning, so a(61) = 0.
A002065(n) mod 64: 0, (1, 3, 13, 55, 9, 27, 53, 47, 17, 51, 29, 39, 25, 11, 5, 31, 33, 35, 45, 23, 41, 59, 21, 15, 49, 19, 61, 7, 57, 43, 37, 63), so a(64) = 32.

Cf. A002065, A328702 (indices to enter the cycles), A290731.

a(n) = my(v=[0],k); for(i=2, n+1, k=(v[#v]^2+v[#v]+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, return(i-j))))

a(n1*n2) = lcm(a(n1),a(n2)) if gcd(n1,n2) = 1.
It seems that for e > 0, a(3^e) = 2; a(5^e) = 1 if e = 1, 4*5^(e-2) otherwise; a(7^e) = 3; a(11^e) = 2 if e = 1, 10*11^(e-2) otherwise; a(13^e) = 3 if e = 1, 12*13^(e-2) otherwise ...
Proof that a(2^e) = 2^(e-1) by induction: we will show that {f(1), f(2), ..., f(2^(e-1))} is a reduced system modulo 2^e, where f is defined in the comment section. It is easy to see that this is true for e = 1, 2.
Suppose that {f(1), f(2), ..., f(2^(e-1))} is a reduced system modulo 2^e, e = 1, 2. For each 1 <= i <= 2^(e-1), f(2^(e-1)+i) - f(i) = Sum_{j=i..2^(e-1)+i-1} (f(j+1)-f(j)) = Sum_{j=i..2^(e-1)+i-1} (f(j)^2+1) = 2^(e-1) + Sum_{j=i..2^(e-1)+i-1} f(j)^2. Of course, {f(i), f(i+1), ..., f(2^(e-1)+i-1)} is also a reduced system modulo 2^e.
Note that if x == y (mod 2^e), then x^2 == y^2 (mod 2^(e+1)). So f(2^(e-1)+i) - f(i) == 2^(e-1) + (1^2+3^2+5^2+...+(2^e-1)^2) == 2^e (mod 2^(e+1)), 1 <= i <= 2^(e-1). This shows that {f(1), f(2), ..., f(2^(e-1)), f(2^(e-1)+1), f(2^(e-1)+2), ..., f(2^e)} is a reduced system modulo 2^(e+1). QED.

cp's OEIS Frontend

A290732 Number of distinct values of X*(3*X-1)/2 mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A376202 Number of pairs 1 <= x <= y <= n-1 such that gcd(x,n) = gcd(y,n) = gcd(x+y,n) = 1 and 1/x + 1/y == 1/(x+y) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

A376203 a(n) = A376202(2*n-1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A376755 a(n) = A376202(6*n+1)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A376756 Number of pairs 0 <= x <= y <= n-1 such that x^2 + x*y + y^2 == 0 (mod n).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A376757 Number of pairs 0 <= x <= y <= n-1 such that x^3 == y^3 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A290727 Analog of A085635, replacing "quadratic residue" (X^2) with "value of X^2+X".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A290728 Analog of A084848, replacing "quadratic residue" (X^2) with "value of X^2+X".

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A290732 Number of distinct values of X(3X-1)/2 mod n.

A317623 Number of distinct values of X(3X-1) mod n.