Your approach takes \$O(n^2)\$ time. Since n can be as large as 100,000, you'll likely need something better. Some benchmarks (inputs are the numbers 1 to n shuffled, and the table shows times in seconds):
n | original AJNeufeld AJ_no_islice Kelly_Bundy
-------+------------------------------------------------
1000 | 0.12 0.07 0.06 0.07
10000 | 11.92 7.98 7.23 0.09
20000 | 50.82 32.83 29.79 0.11
100000 | - - - 0.18
I didn't run the first three solutions on n=100000, they're too slow. AJ_no_islice is the same as AJNeufeld, except with a regular slice instead of islice to demonstrate that islice is not faster but slower.
My solution in a function that takes a list of numbers and returns the result (much better for testing, and for clarity):
def solve(numbers):
incs = [0] * 100001
for numerator, freq in Counter(numbers).items():
for multiple in range(numerator, 100001, numerator):
incs[multiple] += freq
incs = list(accumulate(incs))
return sum(incs[denominator] for denominator in numbers)
It's similar to the sieve of Eratosthenes, though I mark multiples of all numbers, not just of primes. Runtime is O(n log n).
Consider some numerator, let's say 3. Then for every denominator 3 or higher, it contributes 1 to the total. For every denominator 6 or higher, it contributes 2 to the total. And so on. As a table:
incs = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, ...]
So if you then consider some denominator, let's say 7, you simply look up incs[7] to see that it contributes 2 to the total (with the numerator 3).
Now instead consider some other numerator, let's say 4. Its table is:
incs = [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, ...]
Together for numerators 3 and 4:
incs = [0, 0, 0, 1, 2, 2, 3, 3, 4, 5, 5, 5, 7, 7, 7, 8, 9, 9, ...]
How to efficiently compute that table? First only mark the increment spots, e.g., for denominator 3:
incs = [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, ...]
And for denominators 3 and 4 together:
incs = [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0]
And then just accumulate the prefix sums.
Full benchmark code (includes correctness checking):
from timeit import repeat
from random import choices, shuffle
from collections import Counter
from itertools import islice
from itertools import accumulate
def original(numbers):
numbers = sorted(Counter(numbers).items())
sigma = 0
for i in range(len(numbers)):
for j in range(i, len(numbers)):
sigma += (numbers[j][0] // numbers[i][0]) * numbers[j][1] * numbers[i][1]
return sigma
def AJNeufeld(numbers):
numbers = sorted(Counter(numbers).items())
sigma = sum((a_j // a_i) * a_j_count * a_i_count
for i, (a_i, a_i_count) in enumerate(numbers)
for a_j, a_j_count in islice(numbers, i, None))
return sigma
def AJ_no_islice(numbers):
numbers = sorted(Counter(numbers).items())
sigma = sum((a_j // a_i) * a_j_count * a_i_count
for i, (a_i, a_i_count) in enumerate(numbers)
for a_j, a_j_count in numbers[i:])
return sigma
def Kelly_Bundy(numbers):
incs = [0] * 100001
for numerator, freq in Counter(numbers).items():
for multiple in range(numerator, 100001, numerator):
incs[multiple] += freq
incs = list(accumulate(incs))
return sum(incs[denominator] for denominator in numbers)
funcs = original, AJNeufeld, AJ_no_islice, Kelly_Bundy
# Correctness
numbers = choices(range(1, 100001), k=1000)
expect = funcs[0](numbers)
for func in funcs:
result = func(numbers)
print(result == expect, func.__name__,)
print()
# Speed
names = [f' {func.__name__} ' for func in funcs]
print(' n |' + ''.join(names))
print('-------+' + '-' * sum(map(len, names)))
for n in 1000, 10000, 20000, 100000:
print(f'{n:6} |', end='')
numbers = list(range(1, n+1))
shuffle(numbers)
for func in funcs:
if n <= 20000 or func is Kelly_Bundy:
t = min(repeat(lambda: func(numbers), number=1, repeat=1))
t = '%.2f' % t
else:
t = '-'
print(f'{t:>{len(func.__name__)-1}} ', end='')
print()
numbers=[int(number) for number in input.split()]should be sufficient unless I'm missing something \$\endgroup\$