how to deal with large numpy arrays

Question

My problem with this code is that it creates two very large np.arrays for n = 123567101113.

One for the numbers in the form x^2+1 and one for the squared primes.
For the prime numbers I can maybe use sympy.nextprime(), but I don't know what to do with the nums array.

Can I swap them out somehow? My idea would be to make np.array chunks and process as much as possible at the same time.

a) can you store np arrays externally? Or should I put the numbers in a file?
b) is it possible to process np arrays in parallel?
c) the size of the numbers within the array should not necessarily be a problem, should it?
d) does nextprime() or primerange() have a limit?

Thank you very much!
https://sololearn.com/compiler-playground/c0AJ4Fpl5dZd/?ref=app
https://sololearn.com/compiler-playground/c0AJ4Fpl5dZd/?ref=app

Answer 1

A quick search I found numpy support parallelism, and it seems the playground support it.
https://superfastpython.com/numpy-multithreaded-parallelism/

However I'm much more eager to know why C(10) = 9 and C(1000) = 895 or how it is calculated?

Answer 2

The problem of large arrays was avoided in ai. Perhaps you could design the calculations in a similar way.

Answer 3

Wong Hei Ming

This video could be interesting for you: https://youtu.be/Qgevy75co8c?si=SHBN1_g-2Z9PJDWI

while loop is slower than a for loop. And the best thing is to avoid own loops if you can by using in-built functions.

Answer 4

Denise Roßberg
I'm a bit dumb and not fully understand your task at hand.
As I see, C(10) can be express in this way
def C(num):
res = []
for i in range(1, num+1):
res.append(i**2 + 1)
print(res)
[2, 5, 10, 17, 26, 37, 50, 65, 82, 101]

There are 10 elements in res, only 50 is not a square free number.

So, C(10) = 9 means "there are 9 numbers are square free", am I correct?

Answer 5

Wong Hei Ming The range in the second code was wrong. I fixed it. And as I mentioned I used 1,2,3,4...n (just for demonstration). So it gives you all square free nums in a range not only such in form x^2+1

Answer 6

Denise Roßberg
The video is interesting and clear my doubt: is more function call increase the running time?
And I do admit I lack of knowledge of built-in / 3rd party modules.

However day 5 quiz in part 2 the input is insane for me.
It gives 10 sets of data, each set contains a range, in total there are 2,504,127,863 values. For each value it has to go through 7 set of tests. Each set has 1x to 4x sub statement to check against with. If the value gives a True it moves on to the next set early, otherwise it has to check all the sub statement before moving on. And I can't find a "known in advance" pattern in it.

About your task on hand I can't think of any method can solve it within a minute or two. I guess it might have something to do with bitwise operation.

Answer 7

Wong Hei Ming

A square free number is not divisible by a square number > 1:
e g. 10 is square free because 2*5
12 is not square free because 2*2*3, so it's divible by 4
https://oeis.org/A005117

But you need to find square free numbers of the form x^2+1 (2,5,10,17...)

For n = 10 you have the numbers from 2 to 101 and 50 is the only number which is divisible by 25
So C(10) = 9

Hope this helps.

Answer 8

Wong Hei Ming Yep, that's right. And don't feel dumb. It took me also a while to understand the task 😉

Answer 9

I'm feeling dumb because I joined Advent of Code like this.
https://www.sololearn.com/post/1749692/?ref=app

Here is an idea while I'm not familiar with the technique.
We turn it into a generator and check each number is square free or not. If it is not, minus 1 from the original input.

Answer 10

Denise Roßberg

Maybe I use your code wrongly, when I enter 10 & 10, it produces 2 different results and they are not 9.

It is my approach as I described earlier.
https://sololearn.com/compiler-playground/co18g01x8F1a/?ref=app
Apparently it can't handle large number as yours.
But it is my best while it don't throw a "memory error".

And I'm curious how to handle large amount of data.
It is one of the problem in today's advent of code quiz.

Answer 11

Wong Hei Ming

This is how I approached it:

First I looked at the divisors to see if there were squares in them.
But divisors are made up of the prime factors, so you just have to check whether each prime factor only occurs once.
Knowing that sympy only returns unique prime factors, I thought it would be enough to check whether the product of the prime factors is equal to the number to be checked.

If time doesn't play a role, you can even write this as a one-liner (not counting the imports).

https://sololearn.com/compiler-playground/c5DI5kPLhA87/?ref=app

Another approach (but only works for 1,2,3...n):
If a prime factor occurs twice, this is nothing other than a squared prime number: 2*2 = 4, 3*3 = 9, 5*5 = 25, etc.

So in principle, you only have to think about how many numbers are divisible by 4, 9, 25, etc.
n = 20
20//4 - 20//9 = 13

Here you just have to be careful not to take numbers twice if they are divisible e.g. by 4 and by 9 .

Answer 12

Denise Roßberg
Oh...rushed and didn't read the comments......

Answer 13

Can you reply the follow up?