Вдохновленный этим вопросом (Найдите целое число не из четырех миллиардов заданных).
Сколько места для хранения потребовалось бы для хранения целого числа, суммирующего числа от 1 до 4 миллиардов?
Например, 1 + 2 + 3 + 4 + 5 = 15. Суммирование от 1 до 1 миллиона = 500 000 500 000.
Здесь - это алгоритм, который может помочь
Функция, которую вы связываете, чтобы описать, как найти n'th Треугольный номер, который определяется как сумма из n натуральных чисел от 1 до n.
Подставляя 4 миллиарда, поскольку n в функцию дает 8000000002000000000.
Выражая, что, поскольку количество бит может быть выработано, если взять логарифм базы-2 значения и округлить -
ceil (log (8000000002000000000)/log (2)) = 63
Таким образом, требуется 63 бит памяти.
In [12]: import math
In [13]: n=4000000000
In [15]: sumn = n*(n+1)/2
In [16]: sumn
Out[16]: 8000000002000000000L
In [24]: math.log(sumn)/math.log(2)
Out[24]: 62.794705708333197
Ответ: 63 бит.
Один бит - это много, если вы выберете подходящую кодировку для целых чисел.
Вам нужно больше битов n, если есть более 2 ^ n возможных значений, которые вы, возможно, захотите сохранить. Здесь есть только одно значение, которое требуется для хранения.