To see where this comes from, suppose that 2 appears n times in the
prime factorization of x. Choose a single combination of factors higher
than 2, and call its product K. Then divisors of x will include
K * 2^0 (=K),
K * 2^1 (= 2K).
...
K & 2^n
= K ( 1 + 2 + 4 +...) = K * ((2^(n+1))-1)/(2-1)
Adding up all the possible values of K, we see that the sum-of-divisors
is (2^(n+1))/(2-1) times the sum of the divisors that are not multiples
of 2.
Continue the procedure now for primes 3, 5,... to get the formula.
Henry Rich
On 6/10/2014 5:17 PM, Roger Hui wrote:
[image: \sigma_x(n) = \prod_{i=1}^{r}
\frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}]
If you are computing the sum of the divisors Henry's solution is far far
superior. It's based on the above formula. If you can't read it it's
translated into J as follows:
Let p be the primes and e the exponents in the prime factorization of n
(i.e. 'p e'=.__ q: n). x=1 for our purpose. Then the sum of the divisors
is */ ((p^1+e)-1) % p-1 ←→ */ (p^1+e) %&<: p .
On Tue, Jun 10, 2014 at 1:52 PM, 'Pascal Jasmin' via Programming <
[email protected]> wrote:
My solution is incorrect for large inputs sorry. Roger's is fastest
correct solution.
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: "[email protected]" <[email protected]>
Cc:
Sent: Tuesday, June 10, 2014 4:13:43 PM
Subject: Re: [Jprogramming] Shorten a verb
don't know if this is an improvement, but it should be fast
(1 , [: /:~@:~.@:, [: */\"1 (i.@>:@#) |."0 1 ])@:q: 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
----- Original Message -----
From: R.E. Boss <[email protected]>
To: [email protected]
Cc:
Sent: Tuesday, June 10, 2014 3:11:37 PM
Subject: Re: [Jprogramming] Shorten a verb
Remarkably, I was just thinking about such a divisor verb (since I needed
it
to represent an array as a matrix) and came to
(3 :('b, y%|. b=.a#~ 0=y|~ a=.i.&.<: >.%:y'))51
1 3 17 51
(3 :('b, y%|. b=.a#~ 0=y|~ a=.i.&.<: >.%:y'))360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
Or tacitly
(](([, (% |.))]#~ 0=|~) [:i.&.<: >.@%:)
R.E. Boss
(Add your info to http://www.jsoftware.com/jwiki/Community/Demographics )
-----Original Message-----
From: [email protected] [mailto:programming-
[email protected]] On Behalf Of Roger Hui
Sent: dinsdag 10 juni 2014 19:19
To: Programming forum
Subject: Re: [Jprogramming] Shorten a verb
From http://www.jsoftware.com/jwiki/Essays/Divisors
div=: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)
div 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
On Tue, Jun 10, 2014 at 10:10 AM, Jon Hough <[email protected]>
wrote:
My attempt at making a verb that finds the total of all proper divisors
of
an integer seems to work.
e.g. if n = 12, the sum of proper divisors is 1 +2 +3+4+6 = 16 (note 12
is
not included)
This verb is actually equal to the "sigma function" minus n.Wikipedia
explanation: http://en.wikipedia.org/wiki/Divisor_function
(I essentially used the equation for sigma_x(n) where x = 1)
my verb:
sum =.(((*/@:-&1@:{.)%~(*/@:-&1@:({.^(1&+@:,@:}.))))@:(2&p:))-]
This seems ok, but is not aesthetically pleasing, and seems to be very
bracketty, and given that the mathematical equation is pretty concise I
am
surprised the J verb is so long. If anyone knows a nicer way of doing
this
I would be grateful to see it.
Regards.
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
