1

Inspired by this question (Find an integer not among four billion given ones).

How much storage space would it require to store an integer that was the summation of the numbers 1 to 4 billion?

For example, 1+2+3+4+5 = 15. Summation of 1 to 1 million = 500,000,500,000.

Here is an algorithm that may help

Community
  • 1
  • 1
Richard
  • 6,215
  • 4
  • 33
  • 48
  • I can't believe you actually searched the internet for the sum of all numbers from 1 to a million. Use the triangular number identity or even [wolfram alpha](http://www.wolframalpha.com/input/?i=sum+from+1+to+1000000) – Rag Aug 23 '11 at 18:45
  • Umm... That link describes the triangular number formula. Anyways, the question isn't about the value, but the storage requirements. (and not of 1 to 1 million, but 1 to 4 billion) – Richard Aug 23 '11 at 19:02

3 Answers3

9

The function you link to describe how to find the n'th Triangular Number, which is defined as the sum of the n natural numbers from 1 to n.

Substituting 4 billion as n into the function gives 8000000002000000000.

Expressing that as a number of bits can be worked out by taking the base-2 logarithm of the value and rounding up -

ceil(log(8000000002000000000)/log(2)) = 63

So, 63 bits of storage are required.

matja
  • 4,014
  • 3
  • 23
  • 29
9
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

Answer: 63 bits.

Jürgen Strobel
  • 2,200
  • 18
  • 30
5

One bit is plenty, if you choose an appropriate encoding for integers.

You only need more than n bits if there are more than 2^n possible values you could potentially need to store. Here there is only one value that you require to be able to store.

RoundTower
  • 899
  • 5
  • 9