Numbers k whose divisor sum is equal to the divisor sum of k + 1
Numbers k whose divisor sum is equal to the divisor sum of k + 1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Find the numbers k whose divisor sum is equal to the divisor sum of k + 1.
Divisor sum is also known as sigma-sum.
- For example
14 has divisors 1, 2, 7, 14 that sum to 24. 15 has divisors 1, 3, 5, 15 that sum to 24.
So 14 is a member of this sequence.
- Task
Find the first 25 members of this sequence.
- Stretch
Find the first 50 members of this sequence.
- See also
ALGOL 68
Finds the numbers below 1 000 000 (of which there are 62 apparently) without doing any divisions, using a sieve like-approach (as do some of the other samples).
BEGIN # Find n such that the divisor sum of n = the divisor sum of n + 1 #
INT max number = 1 000 000; # maximum number we will consider #
[ 1 : max number ]INT ds; # table of the divisor sums #
ds[ 1 ] := 0;
FOR k FROM 2 TO UPB ds DO ds[ k ] := k + 1 OD;
FOR k FROM 2 TO UPB ds DO
FOR j FROM k + k BY k TO UPB ds DO ds[ j ] +:= k OD
OD;
INT count := 0; # find the numbers #
FOR k TO UPB ds - 1 DO
IF ds[ k ] = ds[ k + 1 ] THEN
print( ( " ", whole( k, -6 ) ) );
IF ( count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD
END- Output:
14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214 111506 116937 122073 138237 147454 161001 162602 166934 174717 190773 193893 201597 230390 274533 289454 347738 383594 416577 422073 430137 438993 440013 445874 455373 484173 522621 544334 605985 621027 649154 655005 685995 695313 739556 792855 937425 949634
Arturo
print.lines select.first:50 1..∞ 'n ->
(sum factors n) = sum factors n+1
- Output:
14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214 111506 116937 122073 138237 147454 161001 162602 166934 174717 190773 193893 201597 230390 274533 289454 347738 383594 416577 422073 430137 438993 440013 445874 455373 484173
BASIC
FreeBASIC
Function SigmaSum(n As Long) As Long
Dim As Long i, sum = 0
For i = 1 To Sqr(n)
If n Mod i = 0 Then
sum += i
If i <> n \ i Then sum += n \ i
End If
Next
Return sum
End Function
Function FormatWithCommas(n As Long) As String
Dim As String result = ""
Dim As String numStr = Trim(Str(n))
Dim As Integer longi = Len(numStr)
Dim As Integer commaPos = ((longi - 1) Mod 3) + 1
For i As Integer = 1 To longi
result &= Mid(numStr, i, 1)
If i = commaPos And i < longi Then
result &= ","
commaPos += 3
End If
Next
Return result
End Function
' Main program
Dim As Long cnt, num, sigmaOfNum, sigmaOfNextNum
cnt = 0
num = 0
While cnt < 50
sigmaOfNum = SigmaSum(num)
sigmaOfNextNum = SigmaSum(num + 1)
If sigmaOfNum = sigmaOfNextNum Then
cnt += 1
Print cnt & ": " & FormatWithCommas(num)
End If
num += 1
Wend
Sleep
- Output:
Same as Raku entry.
Gambas
Function SigmaSum(n As Long) As Long
Dim i As Long, sum As Long = 0
For i = 1 To Sqr(n)
If n Mod i = 0 Then
sum += i
If i <> n \ i Then sum += n \ i
End If
Next
Return sum
End Function
Function FormatWithCommas(n As Long) As String
Dim result As String = ""
Dim numStr As String = Trim(Str(n))
Dim longi As Integer = Len(numStr)
Dim commaPos As Integer = ((longi - 1) Mod 3) + 1
For i As Integer = 1 To longi
result &= Mid(numStr, i, 1)
If i = commaPos And i < longi Then
result &= ","
commaPos += 3
End If
Next
Return result
End Function
Public Sub Main()
Dim cnt As Long = 0, num As Long = 0
Dim sigmaOfNum As Long, sigmaOfNextNum As Long
While cnt < 50
sigmaOfNum = SigmaSum(num)
sigmaOfNextNum = SigmaSum(num + 1)
If sigmaOfNum = sigmaOfNextNum Then
cnt += 1
Print cnt & ": " & FormatWithCommas(num)
End If
num += 1
Wend
End
- Output:
Same as FreeBASIC entry.
OxygenBasic
uses console
function SigmaSum(n as long) as long
long i, sum = 0
for i = 1 to sqr(n)
if n mod i = 0 then
sum += i
if i <> n \ i then sum += n \ i
end if
next
return sum
end function
function FormatWithCommas(n as long) as string
string result = ""
string numStr = rtrim(str(n))
int longi = longi(numStr)
int commaPos = ((longi - 1) mod 3) + 1
int i
for i = 1 to longi
result &= mid(numStr, i, 1)
if i = commaPos and i < longi then
result &= ","
commaPos += 3
end if
next
return result
end function
' Main program
long cnt = 0, num = 0
long sigmaOfNum, sigmaOfNextNum
while cnt < 50
sigmaOfNum = SigmaSum(num)
sigmaOfNextNum = SigmaSum(num + 1)
if sigmaOfNum = sigmaOfNextNum then
cnt += 1
printl cnt & ": " & FormatWithCommas(num)
end if
num += 1
wend
printl cr "Enter ..."
waitkey
- Output:
Same as FreeBASIC entry.
PureBasic
Procedure.l SigmaSum(n.l)
sum.l = 0
For i.l = 1 To Sqr(n)
If n % i = 0
sum + i
If i <> n / i
sum + (n / i)
EndIf
EndIf
Next
ProcedureReturn sum
EndProcedure
Procedure.s FormatWithCommas(n.l)
numStr.s = Str(n)
result.s = ""
longi = Len(numStr)
commaPos = ((longi - 1) % 3) + 1
For i = 1 To longi
result + Mid(numStr, i, 1)
If i = commaPos And i < longi
result + ","
commaPos + 3
EndIf
Next
ProcedureReturn result
EndProcedure
If OpenConsole()
cnt.l = 0
num.l = 0
While cnt < 50
sigmaOfNum.l = SigmaSum(num)
sigmaOfNextNum.l = SigmaSum(num + 1)
If sigmaOfNum = sigmaOfNextNum
cnt + 1
formattedNum.s = FormatWithCommas(num)
PrintN(Str(cnt) + ": " + formattedNum)
EndIf
num + 1
Wend
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
- Output:
Similar to FreeBASIC entry.
QB64
Dim cnt As Long, num As Long, sigmaOfNum As Long, sigmaOfNextNum As Long
cnt = 0
num = 0
While cnt < 50
sigmaOfNum = SigmaSum(num)
sigmaOfNextNum = SigmaSum(num + 1)
If sigmaOfNum = sigmaOfNextNum Then
cnt = cnt + 1
Print cnt; ": "; FormatWithCommas(num)
End If
num = num + 1
Wend
End
Function SigmaSum& (n)
Dim i As Long, sum As Long
sum = 0
For i = 1 To Sqr(n)
If n Mod i = 0 Then
sum = sum + i
If i <> n \ i Then sum = sum + (n \ i)
End If
Next
SigmaSum& = sum
End Function
Function FormatWithCommas$ (n)
Dim result As String, numStr As String
result = ""
numStr = RTrim$(Str$(n))
Dim longi As Integer, commaPos As Integer, i As Integer
longi = Len(numStr)
commaPos = ((longi - 1) Mod 3) + 1
For i = 1 To longi
result = result + Mid$(numStr, i, 1)
If i = commaPos And i < longi Then
result = result + ","
commaPos = commaPos + 3
End If
Next
FormatWithCommas$ = result
End Function
- Output:
Same as FreeBASIC entry.
C
#include <stdio.h>
#include <locale.h>
int divisorSum(int n) {
int i = 3, total = 1, power = 2, sum;
while (!(n % 2)) {
total += power;
power <<= 1;
n >>= 1;
}
while (i * i <= n) {
sum = 1;
power = i;
while (!(n % i)) {
sum += power;
power *= i;
n /= i;
}
total *= sum;
i += 2;
}
if (n > 1) total *= n + 1;
return total;
}
int main() {
const int n = 50;
int res[n];
int i = 2, c = 0, prevSum = 1, currSum;
while (c < n) {
currSum = divisorSum(i);
if (prevSum == currSum) res[c++] = i - 1;
prevSum = currSum;
i++;
}
setlocale(LC_NUMERIC, "en_US.UTF-8");
for (c = 0; c < n; ++c) {
printf("%'7d ", res[c]);
if (!(c + 1)%10) printf("\n");
}
return 0;
}
- Output:
Same as Wren.
C++
#include <cstdint>
#include <iostream>
#include <vector>
int main() {
constexpr uint32_t limit = 500'000;
std::vector<uint32_t> divisor_sums(limit + 1, 0);
for ( uint32_t i = 1; i <= limit; ++i ) {
for ( uint32_t j = i; j <= limit; j += i ) {
divisor_sums[j] += i;
}
}
uint32_t count = 0;
for ( uint32_t i = 0; i < limit; ++i ) {
if ( divisor_sums[i] == divisor_sums[i + 1] ) {
std::cout << ++count << ": " << i << std::endl;
}
}
}
- Output:
Same as the FreeBASIC example.
Dart
import 'dart:math';
int sigmaSum(int n) {
int sum = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
sum += i;
if (i != n ~/ i) {
sum += n ~/ i;
}
}
}
return sum;
}
String formatWithCommas(int n) {
String numStr = n.toString();
String result = '';
int len = numStr.length;
int commaPos = ((len - 1) % 3) + 1;
for (int i = 0; i < len; i++) {
result += numStr[i];
if (i == commaPos - 1 && i < len - 1) {
result += ',';
commaPos += 3;
}
}
return result;
}
void main() {
int count = 0;
int num = 0;
while (count < 50) {
int sigmaOfNum = sigmaSum(num);
int sigmaOfNextNum = sigmaSum(num + 1);
if (sigmaOfNum == sigmaOfNextNum) {
count++;
String formattedNum = formatWithCommas(num);
print('$count: $formattedNum');
}
num++;
}
}
- Output:
Same as FreeBASIC entry.
EasyLang
fastfunc sigsum n .
i = 1
while i <= sqrt n
if n mod i = 0
sumdiv += i
if i <> n div i : sumdiv += n div i
.
i += 1
.
return sumdiv
.
while cnt < 50
if sigsum num = sigsum (num + 1)
cnt += 1
write num & " "
.
num += 1
.- Output:
14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214 111506 116937 122073 138237 147454 161001 162602 166934 174717 190773 193893 201597 230390 274533 289454 347738 383594 416577 422073 430137 438993 440013 445874 455373 484173
J
First we search divisors of argument in the range 1 .. sqrt(arg). Then, we concatenate this list with the application of division of theses numbers with the argument. It allow fast search of divisors. We give to this verb all number betweem 2 to 11000. Then, we apply addition by right reduce. We apply an equality test for each 2-grams of the sequence, check for indices of ones, then add 2.
2+I.2=/\((%([:+/,)])[:I.@:=&0]|~[:i.>.@%:)"0]2+i.110000
Returns : 14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214
And
(2+I.2=/\((%([:+/,)])[:I.@:=&0]|~[:i.>.@%:)"0]2+i.500000
Returns :
14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214 111506 116937 122073 138237 147454 161001 162602 166934 174717 190773 193893 201597 230390 274533 289454 347738 383594 416577 422073 430137 438993 440013 445874 455373 484173
Using timex on intel core i3 with 8gb ram, the first one runs in 0.173346 seconds and the second in 1.08598 seconds.
Java
public final class NumbersKWhoseDivisorSumIsEqualToTheDivisorSumOfKPlus1 {
public static void main(String[] args) {
final int limit = 500_000;
int[] divisorSums = new int[limit + 1];
for ( int i = 1; i <= limit; i++ ) {
for ( int j = i; j <= limit; j += i ) {
divisorSums[j] += i;
}
}
int count = 0;
for ( int i = 0; i < limit; i++ ) {
if ( divisorSums[i] == divisorSums[i + 1] ) {
System.out.println(++count + ": " + i);
}
}
}
}
- Output:
Same as the FreeBASIC example.
Julia
function sigma_sum(n::Int)
sum_divisors = 0
for i in 1:isqrt(n)
if n % i == 0
sum_divisors += i
if i != n ÷ i
sum_divisors += n ÷ i
end
end
end
return sum_divisors
end
function format_with_commas(n::Int)
return replace(string(n), r"(?<=[0-9])(?=(?:[0-9]{3})+(?![0-9]))" => ",")
end
function main()
cnt = 0
num = 0
while cnt < 50
sigma_of_num = sigma_sum(num)
sigma_of_next_num = sigma_sum(num + 1)
if sigma_of_num == sigma_of_next_num
cnt += 1
formatted_num = format_with_commas(num)
println("$cnt: $formatted_num")
end
num += 1
end
end
main()
- Output:
Same as FreeBASIC entry.
PARI/GP
default(parisize, "32M"); \\ Increase to 32MB, adjust if necessary
print(select(x->sigma(x)==sigma(x+1), vector(484173,i,i)))- Output:
[14, 206, 957, 1334, 1364, 1634, 2685, 2974, 4364, 14841, 18873, 19358, 20145, 24957, 33998, 36566, 42818, 56564, 64665, 74918, 79826, 79833, 84134, 92685, 109214, 111506, 116937, 122073, 138237, 147454, 161001, 162602, 166934, 174717, 190773, 193893, 201597, 230390, 274533, 289454, 347738, 383594, 416577, 422073, 430137, 438993, 440013, 445874, 455373, 484173]
Phix
constant n = 62 -- 2.8s, vs 1.2s for 50, 40s for 100
sequence res = repeat(0,n)
int i = 2, c = 1, cursum = 1, nxtsum
while c<=n do
nxtsum = sum(factors(i,1))
if cursum=nxtsum then
res[c] = i-1
c += 1
end if
cursum = nxtsum
i += 1
end while
string fmt = sprintf("%%,%dd",length(sprintf("%,d",res[$])))
printf(1," %s\n",{join_by(res,1,10," ","\n ",fmt:=fmt)})
- Output:
14 206 957 1,334 1,364 1,634 2,685 2,974 4,364 14,841 18,873 19,358 20,145 24,957 33,998 36,566 42,818 56,564 64,665 74,918 79,826 79,833 84,134 92,685 109,214 111,506 116,937 122,073 138,237 147,454 161,001 162,602 166,934 174,717 190,773 193,893 201,597 230,390 274,533 289,454 347,738 383,594 416,577 422,073 430,137 438,993 440,013 445,874 455,373 484,173 522,621 544,334 605,985 621,027 649,154 655,005 685,995 695,313 739,556 792,855 937,425 949,634
Alternative
constant maxnum = 10_000_000
sequence divisor_sums = tagset(maxnum+2,2),
res = {}
divisor_sums[1] := 1
for k:=2 to maxnum do
integer j = k+k
while j<=maxnum do
divisor_sums[j] += k
j += k
end while
end for
for k:=1 to maxnum do
if divisor_sums[k]==divisor_sums[k+1] then
res &= k
end if
end for
string fmt = sprintf("%%,%dd",length(sprintf("%,d",res[$])))
printf(1," %s\n",{join_by(res,1,10," ","\n ",fmt:=fmt)})
- Output:
As above but (wider and) ending with
937,425 949,634 1,154,174 1,174,305 1,187,361 1,207,358 1,238,965 1,642,154 1,670,955 1,765,664 1,857,513 2,168,906 2,284,814 2,305,557 2,913,105 3,296,864 3,477,435 3,571,905 3,582,224 3,682,622 3,726,009 4,328,937 4,473,782 4,481,985 4,701,537 4,795,155 5,002,335 5,003,738 5,181,045 5,351,175 5,446,425 5,459,024 5,517,458 6,309,387 6,431,732 6,444,873 6,514,995 6,771,405 7,192,917 7,263,944 7,796,438 7,845,386 7,955,492 8,428,125 8,561,817 9,279,332 9,293,427 9,309,464 9,309,754 9,359,469 9,577,557 9,669,915 9,693,818
Python
#!/usr/bin/python3
import math
def sigma_sum(n):
sum_divisors = 0
for i in range(1, int(math.sqrt(n)) + 1):
if n % i == 0:
sum_divisors += i
if i != n // i:
sum_divisors += n // i
return sum_divisors
def format_with_commas(n):
return f"{n:,}"
def main():
cnt = 0
num = 0
while cnt < 50:
sigma_of_num = sigma_sum(num)
sigma_of_next_num = sigma_sum(num + 1)
if sigma_of_num == sigma_of_next_num:
cnt += 1
formatted_num = format_with_commas(num)
print(f"{cnt}: {formatted_num}")
num += 1
if __name__ == "__main__":
main()
- Output:
Same as FreeBASIC entry.
Raku
use Prime::Factor;
use Lingua::EN::Numbers;
say ++$, ': ', .&comma for (^Inf).hyper.grep( {
state $next = .&sigma-sum;
my $test = $next == my $this = ($_ + 1).&sigma-sum;
$next = $this;
$test
})[^50];
- Output:
1: 14 2: 206 3: 957 4: 1,334 5: 1,364 6: 1,634 7: 2,685 8: 2,974 9: 4,364 10: 14,841 11: 18,873 12: 19,358 13: 20,145 14: 24,957 15: 33,998 16: 36,566 17: 42,818 18: 56,564 19: 64,665 20: 74,918 21: 79,826 22: 79,833 23: 84,134 24: 92,685 25: 109,214 26: 111,506 27: 116,937 28: 122,073 29: 138,237 30: 147,454 31: 161,001 32: 162,602 33: 166,934 34: 174,717 35: 190,773 36: 193,893 37: 201,597 38: 230,390 39: 274,533 40: 289,454 41: 347,738 42: 383,594 43: 416,577 44: 422,073 45: 430,137 46: 438,993 47: 440,013 48: 445,874 49: 455,373 50: 484,173
Wren
import "./math" for Int
import "./fmt" for Fmt
var n = 50
var res = []
var prevSum = 1
var i = 2
while (res.count < n) {
var currSum = Int.divisorSum(i)
if (prevSum == currSum) res.add(i-1)
prevSum = currSum
i = i + 1
}
Fmt.tprint("$,7d", res, 10)
- Output:
14 206 957 1,334 1,364 1,634 2,685 2,974 4,364 14,841 18,873 19,358 20,145 24,957 33,998 36,566 42,818 56,564 64,665 74,918 79,826 79,833 84,134 92,685 109,214 111,506 116,937 122,073 138,237 147,454 161,001 162,602 166,934 174,717 190,773 193,893 201,597 230,390 274,533 289,454 347,738 383,594 416,577 422,073 430,137 438,993 440,013 445,874 455,373 484,173
XPL0
def MaxNumber = 1_000_000; \maximum number we will consider
def UPB_DS = MaxNumber;
int DS(MaxNumber+1); \table of the divisor sums
int K, J, Count;
begin \Find N such that the divisor sum of N = the divisor sum of N+1
DS(1):= 0;
for K:= 2 to UPB_DS do DS(K):= K+1;
for K:= 2 to UPB_DS do
for J:= K+K to UPB_DS do
begin
DS(J):= DS(J)+K;
J:= J+K-1;
end;
Count:= 0; \find the numbers
Format(7, 0);
for K:= 1 to UPB_DS-1 do
if DS(K) = DS(K+1) then
begin
RlOut(0, float(K));
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0);
end;
end- Output:
14 206 957 1334 1364 1634 2685 2974 4364 14841 18873 19358 20145 24957 33998 36566 42818 56564 64665 74918 79826 79833 84134 92685 109214 111506 116937 122073 138237 147454 161001 162602 166934 174717 190773 193893 201597 230390 274533 289454 347738 383594 416577 422073 430137 438993 440013 445874 455373 484173 522621 544334 605985 621027 649154 655005 685995 695313 739556 792855 937425 949634