A067439 -id:A067439 - cp's OEIS frontend

A340731 Numbers k such that A067439(k) is prime.

10, 15, 25, 27, 29, 31, 33, 36, 37, 44, 54, 64, 69, 78, 81, 82, 88, 102, 106, 110, 121, 142, 148, 177, 183, 192, 211, 212, 240, 270, 272, 274, 280, 314, 332, 337, 338, 344, 367, 381, 384, 404, 412, 421, 429, 434, 460, 463, 467, 490, 502, 511, 519, 523, 530, 551, 559, 584, 586, 588, 614, 624, 628

Offset: 1

J. M. Bergot and Robert Israel, Jan 17 2021

nonn

			a(3) = 25 is a term because A067439(25) = 83 is prime.

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

Cf. A067439, A340736.

filter:= proc(n) local t,k;
   isprime(add(`if`(igcd(n,k)=1, n mod k, 0),k=2..n-1))
end proc:
select(filter, [$1..1000]);

isok(n) = isprime(sum(i=1, n-1, if(gcd(n, i)==1, n%i))); \\ Michel Marcus, Jan 18 2021

A340736 Prime values in A067439, in the order in which they appear.

Original entry on oeis.org

5, 19, 83, 89, 151, 167, 107, 71, 233, 163, 173, 359, 523, 317, 751, 569, 613, 587, 941, 823, 2293, 1741, 1873, 3541, 3907, 2179, 7817, 3907, 2683, 3433, 6277, 6577, 4787, 8807, 9661, 20051, 9403, 10267, 23909, 16927, 8779, 14437, 14887, 31231, 18191, 13883, 14281, 37987, 38839, 14629, 22159

Offset: 1

J. M. Bergot and Robert Israel, Jan 18 2021

nonn

3907 occurs twice, as a(25) and a(28). Are there any others?

			a(3) = 83 because 83 = A067439(25) is the third prime value to occur in A067439.

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

Cf. A067439, A340731.

f:= proc(n) local t, k;
   t:= add(`if`(igcd(n, k)=1, n mod k, 0), k=2..n-1);
   if isprime(t) then t fi
end proc:
map(f, [$1..1000]);

a(n) = A067439(A340731(n)).

A237877 Numbers n such that n | A067439(n).

Original entry on oeis.org

1, 2, 9, 11, 17, 48, 57, 427, 533, 1661, 2161, 4441, 5428, 41628, 171441, 411735, 555716, 1278525, 4292829, 5174373, 8758407, 680133057

Offset: 1

Paolo P. Lava, Feb 14 2014

a(19) > 3000000. - Giovanni Resta, Feb 17 2014

a(23) > 4 * 10^9. - Hiroaki Yamanouchi, Sep 27 2015

			48 is coprime to 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47. When 48 is divided by these numbers the remainders are 0, 3, 6, 4, 9, 14, 10, 2, 23, 19, 17, 13, 11, 7, 5, 1. Their sum is 144 and 144 / 48 = 3.

Cf. A067439.

with(numtheory);P:=proc(q) local i,n,t; for n from 1 to q do t:=0;
for i from 2 to n-1 do if gcd(i,n)=1 then t:=t+(n mod i); fi; od;
if type(t/n,integer) then print(n); fi; od; end: P(10^6);

is(n)=sum(i=1, n-1, if(gcd(n, i)==1, n%i))%n==0 \\ Charles R Greathouse IV, Nov 06 2014

a(14) from Michel Marcus, Feb 17 2014
a(15)-a(18) from Giovanni Resta, Feb 17 2014
a(19)-a(22) from Hiroaki Yamanouchi, Sep 27 2015

A004125 Sum of remainders of n mod k, for k = 1, 2, 3, ..., n.

Original entry on oeis.org

0, 0, 1, 1, 4, 3, 8, 8, 12, 13, 22, 17, 28, 31, 36, 36, 51, 47, 64, 61, 70, 77, 98, 85, 103, 112, 125, 124, 151, 138, 167, 167, 184, 197, 218, 198, 233, 248, 269, 258, 297, 284, 325, 328, 339, 358, 403, 374, 414, 420, 449, 454, 505, 492, 529, 520, 553, 578, 635, 586, 645, 672

Offset: 1

N. J. A. Sloane, Jeffrey Shallit

Row sums of A051778, A048158. Antidiagonal sums of A051127. - L. Edson Jeffery, Mar 03 2012
Let u_m(n) = Sum_{k=1..n} (n^m mod k^m) with m integer. As n-->+oo, u_m(n) ~ (n^(m+1))*(1-(1/(m+1))*Zeta(1+1/m)). Proof: using Riemann sums, we have u_m(n) ~ (n^(m+1))*int(((1/x)[nonascii character here])*(1-floor(x^m)/(x^m)),x=1..+oo) and the result follows. - Yalcin Aktar, Jul 30 2008 [x is the real variable of integration. The nonascii character (which was illegible in the original message) is probably some form of multiplication sign. I suggest that we leave it the way it is for now. - N. J. A. Sloane, Dec 07 2014]
Also the alternating row sums of A236112. - Omar E. Pol, Jan 26 2014
If n is prime then a(n) = a(n-1) + n - 2. - Omar E. Pol, Mar 19 2014
If n is a power of 2 greater than 1, then a(n) = a(n-1). - David Morales Marciel, Oct 21 2015
It appears that if n is an even perfect number, then a(n) = a(n-1) - 1. - Omar E. Pol, Oct 21 2015
Partial sums of A235796. - Omar E. Pol, Jun 26 2016
Aside from a(n) = a(n-1) for n = 2^m, the only values appearing more than once among the first 6*10^8 terms are those at n = 38184 +- 1, 458010 +- 1, 776112 +- 1, 65675408 +- 1, and 113393280 +- 2. - Trevor Cappallo, Jun 07 2021
The off-by-1 terms in the comment above are the terms of A068077. Proof: If a(n-1) = a(n+1), then (n-1)^2 - Sum_{k=1..n-1} sigma(k) = (n+1)^2 - Sum_{k=1..n+1} sigma(k) via the formula; rearranging terms gives sigma(n)+sigma(n+1)=4n. - Lewis Chen, Sep 24 2021

			a(5) = 4. The remainder when 5 is divided by 2,3,4 respectively is 1,2,1 and their sum = 4.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..2000 (first 1000 terms from T. D. Noe)
Jeffrey Shallit, Problem E2817, Amer. Math. Monthly, vol. 87, p 137, 1980.

Cf. A000290, A006218, A023196, A048158, A050482, A051778, A120444 (first differences).

Cf. A067439, A072514, A111490.

List([1..70],n->n^2-Sum([1..n],k->Sigma(k))); # Muniru A Asiru, Mar 28 2018

a004125 n = sum $ map (mod n) [1..n]
-- Reinhard Zumkeller, Jan 28 2011

[&+[n mod r: r in [1..n]]: n in [1..70]]; // Bruno Berselli, Jul 06 2014

A004125 := n -> add( modp(n,k), k=2..n); /* much faster and unambiguous; "a mod b" may be mods(a,b) */ # M. F. Hasler, Nov 22 2007

Table[Sum[Mod[n,k],{k,2,n-1}],{n,70}] (* Harvey P. Dale, Nov 23 2011 *)
Accumulate[Table[2n-1-DivisorSigma[1,n],{n,70}]] (* Harvey P. Dale, Jul 11 2014 *)

A004125(n)=sum(k=2,n,n%k) \\ M. F. Hasler, Nov 22 2007

def a(n): return sum(n%k for k in range(1, n))
print([a(n) for n in range(1, 63)]) # Michael S. Branicky, Jun 08 2021

from math import isqrt
def A004125(n): return n**2+((s:=isqrt(n))**2*(s+1)-sum((q:=n//k)*((k<<1)+q+1) for k in range(1,s+1))>>1) # Chai Wah Wu, Oct 21 2023

def a(n): return sum(n.mod(k) for k in (1..n))
print([a(n) for n in (1..62)])  # Peter Luschny, May 12 2025

a(n) = n^2 - Sum_{k=1..n} sigma(k) = A000290(n) - A024916(n), hence asymptotically a(n) = n^2*(1-Pi^2/12) + O(n*log(n)^(2/3)). - Benoit Cloitre, Apr 28 2002. Asymptotics corrected/improved by Charles R Greathouse IV, Feb 22 2015
a(n) = A008805(n-3) + A049798(n-1), for n > 2. - Carl Najafi, Jan 31 2013
a(n) = A000217(n-1) - A153485(n). - Omar E. Pol, Jan 28 2014
G.f.: x^2/(1-x)^3 - (1-x)^(-1) * Sum_{k>=1} k*x^(2*k)/(1-x^k). - Robert Israel, Aug 13 2015
a(n) = Sum_{i=1..n} (n mod i). - Wesley Ivan Hurt, Sep 15 2017
From Ridouane Oudra, May 12 2025: (Start)
a(n) = A067439(n) + A072514(n).
a(n) = Sum_{d|n} d*A067439(n/d).
a(p) = A067439(p), for p prime.
a(p^k) = A072514(p^(k+1))/p, for p prime and k >= 0. (End)
a(n) = A111490(n) - n. - Peter Luschny, May 12 2025

Edited by M. F. Hasler, Apr 18 2015

A244048 Antisigma(n) minus the sum of remainders of n mod k, for k = 1,2,3,...,n.

Original entry on oeis.org

0, 0, 1, 2, 5, 6, 12, 13, 20, 24, 32, 33, 49, 50, 60, 69, 84, 85, 106, 107, 129, 140, 154, 155, 191, 197, 213, 226, 254, 255, 297, 298, 329, 344, 364, 377, 432, 433, 455, 472, 522, 523, 577, 578, 618, 651, 677, 678, 754, 762, 805, 826

Offset: 1

Omar E. Pol, Jun 23 2014

nonn

For n > 1 a(n) is the sum of all aliquot parts of all positive integers < n. - Omar E. Pol, Mar 27 2021

			From _Omar E. Pol_, Mar 27 2021: (Start)
The following diagrams show a square dissection into regions that are the symmetric representation of A000203, A004125, A153485 and this sequence.
In order to construct every diagram we use the following rules:
At stage 1 in the first quadrant of the square grid we draw the symmetric representation of sigma(n) using the two Dyck paths described in the rows n and n-1 of A237593.
At stage 2 we draw a pair of orthogonal line segments (if it's necessary) such that in the drawing appears totally formed a square n X n. The area of the region that is above the symmetric representation of sigma(n) equals A004125(n).
At stage 3 we draw a zig-zag path with line segments of length 1 from (0,n-1) to (n-1,0) such that appears a staircase with n-1 steps. The area of the region (or regions) that is below the symmetric representation of sigma(n) and above the staircase equals a(n).
At stage 4 we draw a copy of the symmetric representation of A004125(n) rotated 180 degrees such that one of its vertices is the point (0,0). The area of the region (or regions) that is above of this region and below the staircase equals A153485(n).
Illustration for n = 1..6:
.                                                                    _ _ _ _ _ _
.                                                     _ _ _ _ _     |_ _ _  |_ R|
.                                        _ _ _ _ R   |_ _S_|  R|    | |_T | S |_|
.                             _ _ _ R   |_ _  |_|    | |_  |_ _|    |   |_|_ _  |
.                    _ _     |_S_|_|    | |_|_S |    |_U_|_T | |    |_  U |_T | |
.             _ S   |_ S|   U|_|_|S|    |_ U|_| |    |   | |_|S|    | |_    |_| |
.            |_|    |_|_|    |_|_|_|    |_|_ _|_|    |_V_|_U_|_|    |_V_|_ _ _|_|
.                  U        V   U       V
.
n:            1       2         3           4             5               6
R: A004125    0       0         1           1             4               3
S: A000203    1       3         4           7             6              12
T: a(n)       0       0         1           2             5               6
U: A153485    0       1         2           5             6              12
V: A004125    0       0         1           1             4               3
.
Illustration for n = 7..9:
.                                                      _ _ _ _ _ _ _ _ _
.                                _ _ _ _ _ _ _ _      |_ _ _S_ _|       |
.            _ _ _ _ _ _ _      |_ _ _ _  |     |     | |_      |_ _ R  |
.           |_ _S_ _|     |     | |_    | |_ R  |     |   |_    |_ S|   |
.           | |_    |_ R  |     |   |_  |_S |_ _|     |     |_  T |_|_ _|
.           |   |_  T |_ _|     |     |_T |_ _  |     |_ _    |_      | |
.           |_ _  |_    | |     |_ _  U |_    | |     |   |  U  |_    | |
.           |   |_U |_  |S|     |   |_    |_  | |     |   |_ _    |_  |S|
.           |  V  |   |_| |     |  V  |     |_| |     |  V    |     |_| |
.           |_ _ _|_ _ _|_|     |_ _ _|_ _ _ _|_|     |_ _ _ _|_ _ _ _|_|
.
n:                 7                    8                      9
R: A004125         8                    8                     12
S: A000203         8                   15                     12
T: a(n)           12                   13                     20
U: A153485        13                   20                     24
V: A004125         8                    8                     12
.
Illustration for n = 10..12:
.                                                         _ _ _ _ _ _ _ _ _ _ _ _
.                              _ _ _ _ _ _ _ _ _ _ _     |_ _ _ _ _ _  |         |
.     _ _ _ _ _ _ _ _ _ _     |_ _ _S_ _ _|         |    | |_        | |_ _   R  |
.    |_ _ _S_ _  |       |    | |_        |      R  |    |   |_      |     |_    |
.    | |_      | |_  R   |    |   |_      |_        |    |     |_    |_  S   |   |
.    |   |_    |_ _|_    |    |     |_      |_      |    |       |_    |_    |_ _|
.    |     |_      | |_ _|    |       |_   T  |_ _ _|    |         |_ T  |_ _ _  |
.    |       |_ T  |_ _  |    |_ _ _    |_        | |    |_ _        |_        | |
.    |_ _      |_      | |    |     |_ U  |_      | |    |   |    U    |_      | |
.    |   |_ U    |_    |S|    |       |_    |_    |S|    |   |_          |_    | |
.    |     |_      |_  | |    |         |     |_  | |    |     |_ _        |_  | |
.    |  V    |       |_| |    |  V      |       |_| |    |  V      |         |_| |
.    |_ _ _ _|_ _ _ _ _|_|    |_ _ _ _ _|_ _ _ _ _|_|    |_ _ _ _ _|_ _ _ _ _ _|_|
.
n:            10                         11                          12
R: A004125    13                         22                          17
S: A000203    18                         12                          28
T: a(n)       24                         32                          33
U: A153485    32                         33                          49
V: A004125    13                         22                          17
.
Note that in the diagrams the symmetric representation of a(n) is the same as the symmetric representation of A153485(n-1) rotated 180 degrees.
The original examples (dated Jun 24 2014) were only the diagrams for n = 11 and n = 12. (End)

Paolo Xausa, Table of n, a(n) for n = 1..10000

Also zero together with A153485.

Cf. A000203, A000290, A001065, A067439, A024816, A024916, A067439, A123327, A196020, A236104, A237270, A237271, A237593, A244049, A244251, A262626, A342344.

With[{r=Range[100]},Join[{0},Accumulate[DivisorSigma[1,r]-r]]] (* Paolo Xausa, Oct 16 2023 *)

from math import isqrt
def A244048(n): return (-n*(n-1)-(s:=isqrt(n-1))**2*(s+1) + sum((q:=(n-1)//k)*((k<<1)+q+1) for k in range(1,s+1)))>>1 # Chai Wah Wu, Oct 22 2023

a(n) = A024816(n) - A004125(n).
a(n) = A000217(n) - A000203(n) - A004125(n).
a(n) = A024916(n) - A000203(n) - A000217(n-1).
a(n) = A000217(n) - A123327(n).
a(n) = A153485(n-1), n >= 2.

A340740 a(n) is the sum of all the remainders when n is divided by positive integers less than n/2 and coprime to n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 2, 2, 1, 7, 2, 7, 6, 5, 4, 15, 7, 19, 10, 9, 8, 32, 9, 20, 20, 28, 13, 46, 14, 47, 31, 27, 31, 48, 17, 62, 39, 58, 26, 87, 26, 94, 53, 52, 41, 127, 48, 100, 65, 79, 61, 154, 52, 105, 62, 90, 80, 200, 45, 180, 113, 138, 103, 162, 77, 229, 116, 149, 73, 274, 87, 257, 166, 178

Offset: 1

J. M. Bergot and Robert Israel, Jan 18 2021

			For n = 11, a(11) = (11 mod 1)+(11 mod 2)+(11 mod 3)+(11 mod 4)+(11 mod 5) = 7.

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

Cf. A067439.

f:= proc(n) local k;
  add(`if`(igcd(k,n)=1, n mod k, 0),k=1..floor(n/2))
end proc:
map(f, [$1..100]);

Table[Sum[Mod[n, i]*Floor[1/GCD[i, n]], {i, Floor[(n - 1)/2]}], {n,
100}] (* Wesley Ivan Hurt, Jan 18 2021 *)

a(n) = sum(k=1, n\2, if (gcd(k, n)==1, n%k)); \\ Michel Marcus, Jan 18 2021

from math import gcd
def A340740(n): return sum(n % k for k in range(1,n//2+1) if gcd(k,n) == 1) # Chai Wah Wu, Mar 18 2021

a(n) = Sum_{k=1..floor((n-1)/2)} (n mod k) * floor(1/gcd(n,k)). - Wesley Ivan Hurt, Jan 18 2021

A072514 Sum of n mod k for k in {1...n} with gcd(k,n) > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 2, 3, 8, 0, 9, 0, 16, 17, 16, 0, 27, 0, 31, 31, 44, 0, 52, 20, 56, 36, 69, 0, 92, 0, 72, 77, 102, 68, 127, 0, 128, 97, 152, 0, 192, 0, 165, 153, 196, 0, 230, 56, 231, 170, 237, 0, 319, 154, 290, 211, 302, 0, 421, 0, 334, 273, 334, 192, 478, 0, 411, 317

Offset: 1

Amarnath Murthy, Jul 30 2002

nonn

Previous name was: Sum of the remainders when n is divided by unrelated numbers (numbers which are neither coprime to n nor divide n).

			a(18) = 27: the unrelated numbers to 18 are 4, 8, 10, 12, 14, 15 and 16. The remainders when 18 is divided by these numbers are 2, 2, 8, 6, 4, 3 and 2 whose sum is 27.

Paolo P. Lava, Table of n, a(n) for n = 1..1000

Cf. A004125, A067439, A008683, A111490.

seq(add(n mod k, k=select(j->gcd(j,n)>1, [$1..n])),n=1..69); # Peter Luschny, Oct 01 2014

snmk[n_]:=Total[Mod[n,Complement[Complement[Range[n],Divisors[n]], Select[ Range[n], CoprimeQ[ #,n]&]]]]; Array[snmk,70] (* Harvey P. Dale, Dec 09 2018 *)

lista(nn) = vector(nn, n, sum(i=1, n, (n % i)*(gcd(n, i) != 1))); \\ Michel Marcus, Oct 01 2014

From Ridouane Oudra, May 14 2025: (Start)
a(n) = A004125(n) - A067439(n).
a(n) = Sum_{d|n, d>1} d*A067439(n/d).
a(p) = 0, for p prime.
a(p*q) = p*A067439(q) + q*A067439(p), for p and q two distinct prime numbers.
a(p^k) = p*A004125(p^(k-1)), for p a prime and k >= 0. (End)

Corrected and extended by David Garber, Oct 22 2002

New name from Robert Israel, Oct 01 2014

cp's OEIS Frontend

A340731 Numbers k such that A067439(k) is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

A340736 Prime values in A067439, in the order in which they appear.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A237877 Numbers n such that n | A067439(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Extensions

A004125 Sum of remainders of n mod k, for k = 1, 2, 3, ..., n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

SageMath

Formula

Extensions

A244048 Antisigma(n) minus the sum of remainders of n mod k, for k = 1,2,3,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A340740 a(n) is the sum of all the remainders when n is divided by positive integers less than n/2 and coprime to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A072514 Sum of n mod k for k in {1...n} with gcd(k,n) > 1.