I can't find an answer to this

n is a positive integer with exactly 9 divisors.
the sum of the divisors equals 187131

I cannot find an answer to this shit, halp?

Bruteforce it with CUDA

project euler?

/prog/ - Homework

σ₀(n) = 9
σ₁(n) = 187131

http://en.wikipedia.org/wiki/Divisor_function

n = 106276
n = 165649

http://www.research.att.com/~njas/sequences/?q=187131

THE QUEEREST QUESTION

In[1]:= Select[Range[200000],
 DivisorSigma[0, #] == 9 && DivisorSigma[1, #] == 187131 &]

Out[1]= {106276, 165649}

--posted from my mathematica cuda

>>8
PARI/GP is also acceptable because it isn't written by computer science amateurs

There are 2 such numbers: 106276 165649.

If you knew a bit of elementary math, you'd know that every natural number can be decomposed as a product of prime numbers at various powers and such decomposition is unique, not only that, but tau can be calculated knowing this decomposition.

Now we look at tau(n) = 9.
We know 9 = 3*3.

And we know that for n = p₁^a₁*...*p_k^a_k.
and for such an n, tau(n) = product(a_i+1), where i from 1 to k.

So, for 9 we can have n = p**8. or n = p₁² * p₂²

We examine the first case, where n = p**8, we'll see that the sum of divisors in this case is a geometric progression, and the sum is 1+p+p**2+...+p**8. If p = 2, sum is 2**9-1 = 511, which is too small, if p = 3... I'll just write a small piece of code to check these values:

(loop for j from 1 to 4 collect
      (loop for i from 1 to 9
        summing (expt j i)))
;=>(9 1022 29523 349524)
So after p = 3, we go out of range (187131).
This means we either have case 2 or we have no solutions.

In case 2, we know that the number is of the form n = p₁² * p₂², or written differently n = (p₁* p₂)², or that it's a square of the product of 2 primes. We know that the sigma function is greater than n+1. Which gives us a search range for p1*p2 of square root of 187131, or approximatively 2..433.

While if you were to search by hand, it would give you results rather soon, I reused some crappy code I wrote some time ago:

(defun seq (n m &optional (k 1))
  (loop for i from n to m by k collect i))

(define-modify-macro set-differencef (&rest args) set-difference)

(defun primes (n)
  (let ((primes (seq 2 n 1)))
    (loop for i in primes
          do (set-differencef primes (rest (seq i n i))))
    (sort primes #'<)))

Now I wrote some terrible, hard-coded code which should have been done using a macro to search for it:

(let ((primes (primes 433))) 
  (dolist (prime1 *primes*)
    (dolist (prime2 *primes*)
      (when (> prime2 prime1)
        (when (= (+
                  1
                  prime1
                  prime2
                  (* prime1 prime2)
                  (* prime1 prime2 prime2)                               
                  (* prime1 prime1 prime2)
                  (* prime1 prime1)
                  (* prime2 prime2)
                  (* prime1 prime1 prime2 prime2))
                 187131)
          (print (* prime1 prime2 prime1 prime2)))))))
And we get the results: 106276 and 165649, which are 2*2*163*163 and 11*11*37*37. Had we have searched by hand, we would have reached the results as well, as p1=2 and p1=11 are rather near.

Looks like someone beat me to it >>6,8, damn.

>>11
It's because you don't have that fresh cuda power

>>1
Is there some interpretation to this problem I am not understanding or is my head dense at the moment?

n is a positive integer and has nine (unique?) divisors.  That is:
a * b * c * d * e * f * g * h * i = n
You can divide n by a...i without remainder.
The sum of the divisors is 187131.  That is:
a + b + c + d + e + f + g + h + i = 187131

Everything I'm reading makes me think something is wrong with that analysis.

>>13
There's nothing to say that the product of the divisors equals n. Every number has a unique representation as a product of primes (also known as the fundamental theorem of arithmetic). Given a representation like n = p₁^a₁ * p₂ ^ a₂ * ... * p_k ^ a_k, the divisors are:
p1^m1 * .. * p_k*m_k, where 0 <= m_k <= a_k. And the number of divisors is just (a₁+1)*...*(a_k+1).

>>13
Divisors aren't always factors.

>>15
That is a lie.

>>16
cake

hi there, OP here
ok so it works

now, how can I be sure there's no other positive integer greater than 187131 that could be n?

>>18
the sum of the divisors equals 187131
You better be trolling.

>>19
sorry. I'm retarded.

>>19
That is sad how long it took for someone to see that

>>20
Or are you?

>>19
What's the problem?