Original Title: Calculating Arithmetic Sequence sum to <= X
The title may sound a little confusing, but I am trying to calculate how many rebirths or n-ths of the arithmetic sequence a user can afford.
An easy solution is to loop through and take the sum of the arithmetic series and brute force the finite series until it finds the biggest solution.
However this would calculate an equation O(n) times and I am sure there is a way to do it in O(1)
TL;DR:
How do I calculate how many rebirths a player can afford with my rebirth system using arithmetic sequence
I have arithmetic progression formula
a1 + (n - 1)d
which relates to the cost of a rebirth. I want to calculate how many sequences it can afford basically. if I wanted to brute force it I can keep checking the sum formula of each number 1-n adding them up until it can’t afford it anymore. (edited)
why not just use your equation you got? (I’m assuming you mean the arithmetic series as in an = a1+(n-1)d)
oh nvm I see I understood the question wrong
From what I can understand, you could try altering a binary search so it finds the highest number less then whatever number you choose, its not O(1) but it’d be pretty fast
----I think this should be the answer V ------
wait no why not just do something like:
treat the number you have as x, then the amount of rebirth you can get would be ceil((x-a1)/d)
I do not understand why you responded this way. I do know what an arithmetic series is, I don’t know if you read the start of my question to understand that I stated that I knew n was the term, a1 is the base and an is the nth term. Likewise, I am just trying to help out here, and it hurts that you just assumed everything I said was trash.
Second, why do you even need a sequence? As I see things right now there is no need for a sequence and it would help if you gave us more context about the problem. No, it isn’t that I simply lack skills of comprehension, rather you are asking for alternative methods to get an O(1) output and for that I need to know if what is being done is even necessary.
(I saw that you edited your message so I’ll read it now)
He’s saying the cost of rebirthing is not a constant value, and it is determined by an arithmetic sequence (basically the base cost of rebirthing is increased per-rebirth)
Ok I have come up with two functions to solve for your answer. Say you want to find the amount of rebirths required to cost 100, then total would be 100. And the delta is 10 per, starting at 10 also.
10 + 20 + 30 + 40 = 100, so 4 rebirths you could get.
My function would tell you the 4 using algebra.
function sumofSequence(upToIndex,delta)
return (((upToIndex* upToIndex) + upToIndex) * (delta/2))
end
function solveSequence(delta,total)
local newTotal = total * 2
newTotal /= delta
local first = (-1 + math.sqrt(1 - (4*-newTotal))) / 2
return first
end
print(solveSequence(10,100)) -- for example, prints 4.
Yes it uses everyone’s favorite formula, the quadratic formula.
Nope, that only finds the nth digit in the sequence smaller then x, while OP wants to find the sum of the series at n digits smaller then x. (what OP wants is a way to find n for n(a1+(a1+(n-1)d))/2 <= x, not n for a1+(n-1)d <= x)
Do you by chance have to floor that? (also, it seems to have not not worked for sequence a1 = 1, delta = 2, x = 4, giving 1.6 rather then an expected 2 or higher, unless you’re meant to ceiling that?)
I suspect this method only works for when delta = a1, which would require OP to alter their scripts a bit. Its definitly better then nothing though
after a bit more testing, it seems like its not an issue with ceiling, since testing with a1 = 1, delta = 3, x = 4 results in a little over 3, when the correct answer should be 2
Say it results that a user could rebirth 10.5 times, that means he can afford 10 full rebirths and almost another one. But not quite 11 rebirths, thus you must always round down.
however, if the sequence has a1 = 1, delta = 2, x = 4, that is not the case, as the resulting answer needs to be rounded UP in order to be correct (being 2 rather then 1)
I understand, however, we cant just assume that a1 = delta for OP, as it is not stated, OP might want to have a1 ~= delta for game design reasons afterall.
For OP, if you are fine with a1 = delta, @AC_Starmarine 's solution is definetly the best, while if you want a1 ~= delta, I believe the solution would be: floor((a1d)+sqrt(d(a^2*d+2x))
Or for easier reading, the floor of
