# Calculating a large sum of positive and negative integers gives wrong answer

**URL:** <https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334>\
**Category:** General Usage\
**Tags:** question, potential-bug\
**Created:** [March 8, 2024, 3:51am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334 "2024-03-08T03:51:57Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![SherlockSage](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sherlocksage/32/207584_2.png) [@SherlockSage](https://discourse.julialang.org/u/SherlockSage)\
**Post date:** [March 8, 2024, 3:51am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/1 "2024-03-08T03:51:57Z")

</div>

Hello! I am trying to solve a Project Euler problem (#193) to get the squarefree integers less than the large number 2^50. I normally wouldn’t just post the code here directly because of spoilers for the problem except I keep getting the wrong answer in base Julia and in Pluto.jl

```julia
using Primes
limit193 = Int64(2)^50-1
sqrt193 = Int64(2)^25-1
function mobius(max_n)
	res = ones(Int8, max_n)
	for p in primes(floor(Int32, sqrt(Int64(max_n))))
		for i = p*p:p*p:max_n
			res[i] = 0
		end
		for i = p:p:max_n
			res[i] *= -1
		end
	end
	res
end
m25 = mobius(Int64(2)^25)
sum(m25[k]*limit193÷k^2 for k = 1:sqrt193)

```

This last line returns `684489637771331` which is not the correct answer (except in the first few digits, which may or may not be a factor). I am summing 33 million positive and negative integers here so maybe I’m hitting some sort of limitation, but I can’t figure out what. Do you guys have any ideas?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [March 8, 2024, 4:03am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/2 "2024-03-08T04:03:47Z")

</div>

this is probably integer overflow. Try doing this with `Int128`

---

<div class="post-metadata">

**Author:** ![screw\_dog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/screw_dog/32/48119_2.png) [@screw\_dog](https://discourse.julialang.org/u/screw_dog)\
**Post date:** [March 8, 2024, 4:11am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/3 "2024-03-08T04:11:04Z")

</div>

Not sure I understand the task here but `mobius` is calculating the Mobius function, right? Which is only ever -1, 0, or 1?

The `sum` is doing an integer division (`÷`) which will rarely be exact, is this intended?

---

<div class="post-metadata">

**Author:** ![SherlockSage](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sherlocksage/32/207584_2.png) [@SherlockSage](https://discourse.julialang.org/u/SherlockSage)\
**Post date:** [March 8, 2024, 4:29am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/4 "2024-03-08T04:29:10Z")

</div>

Yes, that is the Mobius function and the integer division is intended.

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [March 8, 2024, 4:42am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/5 "2024-03-08T04:42:16Z")

</div>

Your Möbius function does not give the same result as

> **[Möbius function - Rosetta Code](https://rosettacode.org/wiki/M%C3%B6bius_function#Julia)**

term 5801 is 1 in your version and -1 with the other (and from there on a lot of other terms are different)

replacing the Möbius function, the final result is 684465067343069 on my machine (no idea if that is actually the right answer)

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 8, 2024, 4:52am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/6 "2024-03-08T04:52:52Z")

</div>

I hate figuring out integer overflows, so try `sum(m25[k]*limit193÷k^2 for k = 1:sqrt193; init=BigInt(0)` and see if you’re lucky enough to get a verified answer. I would try this _after_ you figure out the mobius implementation concern JM\_Beckers raised.

---

<div class="post-metadata">

**Author:** ![SherlockSage](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sherlocksage/32/207584_2.png) [@SherlockSage](https://discourse.julialang.org/u/SherlockSage)\
**Post date:** [March 8, 2024, 4:53am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/7 "2024-03-08T04:53:00Z")

</div>

Aw heck. That’s probably it. Is it okay etiquette if I delete this thread since it’s just a bug on my own part but also it’s a spoiler for a Project Euler problem?  
EDIT: Yeah it was the mobius function. Thanks guys! 😃  
EDIT 2: Gonna leave this thread up because there’s already spoilers elsewhere on the Internet if someone wants to find them. Again, thanks

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 8, 2024, 9:13am UTC](https://discourse.julialang.org/t/calculating-a-large-sum-of-positive-and-negative-integers-gives-wrong-answer/111334/8 "2024-03-08T09:13:29Z")

</div>

Just a few comments:

> [@SherlockSage](#):
>
> `for p in primes(floor(Int32, sqrt(Int64(max_n))))`

Are you on a 32-bit system, because on mine, there’s no `primes` method for `Int32`:

```julia
julia> primes(Int32(11))
ERROR: MethodError: no method matching primes(::Int32)

Closest candidates are:
  primes(::Int64)
   @ Primes C:\Users\DNF\.julia\packages\Primes\Yo1YT\src\Primes.jl:130
  primes(::Int64, ::Int64)
   @ Primes C:\Users\DNF\.julia\packages\Primes\Yo1YT\src\Primes.jl:114

```

I was wondering why you wrapped your literals like this: `Int64(2)`, since that’s not normally needed.

Secondly, it’s safer to use `isqrt(n)` rather than `floor(Int, sqrt(n))`. I struggled a bit to find an example, but here’s one from an old thread using an `Int128`:

> [@Simple prime number test 1000 slower than trivial python?](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/4):
>
> And secondly: `Int(floor(sqrt(n)))`, gives you the wrong number:
> 
> ```julia
> julia> n = 10000001829379821798314198278324234
> 10000001829379821798314198278324234
> 
> julia> Int(floor(sqrt(n))) # you should rather use floor(Int, sqrt(n)), actually
> 100000009146898688
> 
> julia> isqrt(n) # this is the largest integer m such that m^2 < n
> 100000009146898690
> 
> ```