Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the formula $\sum_1^n{i} = \frac{n ( n - 1)}{2} $, does there exist a function $F$ such that $F(n) = i$?

If so, what is it? If not, why not?

share|improve this question
    
I am looking for a function which runs in $O(1)$, not an algorithm for finding the value of $i$ via a search. –  Kyle Polich Mar 6 '12 at 23:15
    
What is $F(n)$ and $i$? –  user17762 Mar 6 '12 at 23:18
    
When you write your sum, do you mean $\sum^{n}_{i=1}i$ (summing as $i$ ranges from 1 to n), $\sum^n_{j=1} i$ (summing $i$ a total of $n$ times), or $\sum^n_{j=1} i(j)$, where $i$ is a function of $j$? –  KReiser Mar 6 '12 at 23:19
    
Could you give an example, it is a bit vague to me. Are you looking for a Hashing algorithm? –  Emmad Kareem Mar 6 '12 at 23:21
    
Bit of a necro, but I used this today and found that I had to use the ceiling function to make the answer an integer, and also found out that I can't reply vice adding a new answer. –  Jared Beekman Apr 2 '13 at 16:07

1 Answer 1

up vote 3 down vote accepted

Maybe you are asking, given $X$, how can I find $n$ such that $\sum_1^ni=X$? or maybe not, it's very hard to tell what you are asking. But if that is what you are asking, here's the answer: multiply $X$ by $8$, add $1$, take the square root, subtract $1$, and divide by $2$.

For example, if $X=45$, you go $45\to360\to361\to19\to18\to9$, and indeed $1+2+\cdots+9=45$.

But your $n(n-1)/2$ should be $n(n+1)/2$.

share|improve this answer
    
Exactly what I was looking for. Thank you! –  Kyle Polich Mar 6 '12 at 23:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.