Ho do I convert pic related into a closed-form expression?
I need a much faster way to compute that shit. I can't use a lookup table (precomputing into an array) because it became too big. I need to compute values up to up to 2^56.
I know about generating functions, but I don't know how to deal with floor().
Other urls found in this thread:
>I need to compute values up to up to 2^56
but that will only give you 57 terms
What you mean?
6n + 0, 0, 1, 1, 3, 3, 4, 4, 7, 7, 8, 8, 10, 10, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 22, 22, 23, 23, 25, 25, 26, 26, 31, 31, 32, 32, 34, 34, 35, 35, 38, 38, 39, 39, 41, 41, 42, 42, 46, 46, 47, 47, 49, 49, 50, 50, 53, 53, 54, 54, 56, 56, 57, 57, 63, 63, 64, 64, 66, 66, 67, 67, 70
I still have the problem to compute the correct element of your sequence given n.
Anyways, it looks easier. Thanks.
Hi folks, the closed result is obtained by looking at the chart to the right, which gives all the insight needed about the result, thanks OP for posting the function's results up to f(10) though, here goes :
[math]f(n)=\lfloor \frac{n+1}{4}\rfloor\left(\lfloor \frac{n+1}{4}\rfloor+1 \right)\frac{1}{2}+\lfloor \frac{n+1}{2}\rfloor+6n[/math]
I didn't actually check whether this is the "correct" sequence, I just substracted 6n from all the values you posted here and put it into this website: oeis.org
It says the function is "a(n) = n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!."
A general formula apparently is: (I assume brackets means floor)
a(n) = a([n/2]) + [n/2] = [n/2] + [n/4] + [n/8] + [n/16] + ...
There are also some other formulas which might be even easier to compute
i fucked it up, my result has the [math]6n[/math] part one off, so it would then be :
[math]f(n+1)=\lfloor \frac{n+1}{4}\rfloor\left(\lfloor \frac{n+1}{4}\rfloor+1\right)+\lfloor \frac{n+1}{2}\rfloor+6(n+1)[/math]
This result, however, is right, take my word for it
Your function works for the first 10 values, after that it grows far faster than OPs function
OP, you should use this formula, and cache and reuse all a(n)s (because you're going to need them again for a(2*n)), this makes it possible to compute all function values in O(n)
I can't post the links because they are detected as spam. I will post a codes you can paste into google short links
>https://
>goo
>(dot)
>gl/
If I past my sequence into oeis.org I get
>Sorry, but the terms do not match anything in the table.
If you wanna check by yourself, here's the short links
Full sequence: oAQTuU (short link)
If I subtract 6n to each element: jEPXzM (short link)
>thanks OP for posting the function's results up to f(10)
There you go, up to 1000: tRWhuN (short link)
If you want more values, you just need to ask. If you want it in another format for an easier copy pasting, just tell me how should I print it.
>A general formula apparently is: (I assume brackets means floor)
>a(n) = a([n/2]) + [n/2] = [n/2] + [n/4] + [n/8] + [n/16] + ...
I didn't checked if it's correct, but computing something like this is as hard as computing the for loop I posted above (OP picture).
I need something much much faster. (if it's possible)
The first one is the sequence I need, the second one is what you get from your formula
> 0, 6, 13, 19, 27, 33, 40, 46, 55, 61, 68, 74, 82, 88, 95, 101, 111, 117, 124, 130, 138, 144, 151, 157
> 0, 6, 13, 19, 28, 34, 41, 47, 58, 64, 71, 77, 90, 96, 103, 109, 124, 130, 137, 143, 160, 166, 173, 179
If you have other ideas feel free to post them. I will check if they are correct.
so which one is it? the top or bottom sequence?
Top is what I want, bottom is what I get from your expression.
I need top, you gave me an expression for bottom.
you fucked up your calculations apparently, geogebra says otherwise for me, pic related
okay i got it
forgot the half factor in the expression, i had it in the first one though, which was false, here is (again) the correct one :
[math]f(n+1)=\lfloor \frac{n+1}{4}\rfloor\left(\lfloor \frac{n+1}{4}\rfloor+1\right)\frac{1}{2}+\lfloor \frac{n+1}{2}\rfloor+6(n+1)[/math]
Top is what I want, bottom is what I get from your expression
> 0, 6, 13, 19, 27, 33, 40, 46, 55, 61, 68, 74, 82, 88, 95, 101, 111, 117, 124, 130, 138, 144, 151, 157
> 0, 6, 13, 19, 27, 33, 40, 46, 55, 61, 68, 74, 84, 90, 97, 103, 114, 120, 127, 133, 145, 151, 158, 164
import math
number = 23523452345
def bitCount(int_type):
count = 0
while(int_type):
int_type &= int_type - 1
count += 1
return(count)
print [ 7*n - bitCount(n) for n in range(1000)]
You're amazing, thanks! It seems to works really well.
how did you figure out this
Yeah its just the 6*n plus n minus the number of set bits in n.
The guy who posted the oasis thing should've looked down the page.
print 7*(2**256-1) - bin(2**256-1)[2:].count('1')
print [7*n - bin(n)[2:].count('1') for n in range(1000)]
this should be even faster according to stack overflow.