Welcome Guest ( Log In | Register )

Outline · [ Standard ] · Linear+

 Coding challenge

views
     
TScodercoder
post May 9 2023, 09:23 AM, updated 3y ago

Getting Started
**
Junior Member
148 posts

Joined: Jan 2023
Try to solve this with any programming language and don't use ChatGPT / google laugh.gif


Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.
jusbella
post May 9 2023, 09:29 AM

Look at all my stars!!
*******
Senior Member
3,038 posts

Joined: Dec 2011


31626
tkhin
post May 9 2023, 01:10 PM

Getting Started
**
Junior Member
120 posts

Joined: Mar 2006


test
tkhin
post May 9 2023, 01:12 PM

Getting Started
**
Junior Member
120 posts

Joined: Mar 2006


test
TScodercoder
post May 9 2023, 01:43 PM

Getting Started
**
Junior Member
148 posts

Joined: Jan 2023
QUOTE(jusbella @ May 9 2023, 09:29 AM)
31626
*
Share code la. How long you took to complete it? icon_rolleyes.gif
angch
post May 9 2023, 01:57 PM

On my way
****
Junior Member
636 posts

Joined: Jul 2006
Easy peasy. 2 minutes.

https://go.dev/play/p/VbK-6Frup6h

31626

CODE
package main

func sumdiv(j int) int {
sum := 1
for i := 2; i < j; i++ {
 if j%i == 0 {
  sum += i
 }
}
return sum
}

func main() {
sum := 0
cache := make(map[int]int)
for i := 1; i < 10000; i++ {
 j, ok := cache[i]
 if !ok {
  j = sumdiv(i)
  cache[i] = j
 }
 if i != j && i == sumdiv(j) {
  sum += i
 }
}
println(sum)
}

angch
post May 9 2023, 02:13 PM

On my way
****
Junior Member
636 posts

Joined: Jul 2006
8 cores, 0.74 seconds on my machine

https://go.dev/play/p/GopMyUOPvOP

CODE

package main

import "sync"

func sumdiv(j int) int {
sum := 1
for i := 2; i < j; i++ {
 if j%i == 0 {
  sum += i
 }
}
return sum
}

func main() {
const MAX = 10000
cache := [MAX + 1]int{}
work := make(chan int, 100)
wg := sync.WaitGroup{}

dowork := func(w chan int) {
 for i := range w {
  j := sumdiv(i)
  cache[i] = j
 }
 wg.Done()
}

// Let's go, 8 cores!
for i := 0; i < 8; i++ {
 wg.Add(1)
 go dowork(work)
}
for i := 1; i < MAX; i++ {
 work <- i
}
close(work)
wg.Wait()
sum := 0
for i := 1; i < MAX; i++ {
 j := cache[i]
 if j > MAX {
  continue
 }
 if i != j && i == cache[j] {
  sum += i
 }
}
println(sum)
}

angch
post May 9 2023, 02:35 PM

On my way
****
Junior Member
636 posts

Joined: Jul 2006
Even faster. 0.14s. sieve of eratosthenes

https://go.dev/play/p/9KECP-Q19K1

CODE

package main

func main() {
const MAX = 10000
cache := [MAX + 1]int{}
cache[1]++

// Construct sieve of eratosthenes
for i := 1; i <= MAX; i++ {
 for j := i + i; j <= MAX; j += i {
  cache[j] += i
 }
}

sum := 0
for i := 1; i < MAX; i++ {
 j := cache[i]
 if j <= MAX && i != j && i == cache[j] {
  sum += i
 }
}
println(sum)
}

angch
post May 9 2023, 02:55 PM

On my way
****
Junior Member
636 posts

Joined: Jul 2006
CODE
angch@mondas code % cat golf.pl
for(1..1e4){for($i=$_*2;$i<=1e4;$i+=$_){$a[$i]+=$_}}
for(1..1e4){$b=$a[$_];$s+=$_ if$_==$a[$b]&&$_!=$b;}
print$s;                                                                                
angch@mondas code % perl golf.pl
31626%  


Of course I have to golf it. 113 bytes.

This post has been edited by angch: May 9 2023, 02:56 PM
TScodercoder
post May 9 2023, 05:16 PM

Getting Started
**
Junior Member
148 posts

Joined: Jan 2023
QUOTE(angch @ May 9 2023, 02:55 PM)
CODE
angch@mondas code % cat golf.pl
for(1..1e4){for($i=$_*2;$i<=1e4;$i+=$_){$a[$i]+=$_}}
for(1..1e4){$b=$a[$_];$s+=$_ if$_==$a[$b]&&$_!=$b;}
print$s;                                                                                
angch@mondas code % perl golf.pl
31626%  


Of course I have to golf it. 113 bytes.
*
Pro coder notworthy.gif rclxms.gif
flashang
post May 10 2023, 12:10 AM

Casual
***
Junior Member
355 posts

Joined: Aug 2021


after convert angch's code,
only some jit engine could beat go's speed.

smile.gif



This post has been edited by flashang: May 10 2023, 12:29 AM
angch
post May 10 2023, 10:42 AM

On my way
****
Junior Member
636 posts

Joined: Jul 2006
QUOTE(flashang @ May 10 2023, 12:10 AM)
after convert angch's code,
only some jit engine could beat go's speed.

smile.gif
*
If you optimize it further, you can't really beat this for speed:

CODE
echo 31626


ie, @jusbella's solution is faster than any of mine.

Ahead of time compiler >> Just in time compilers.

This post has been edited by angch: May 10 2023, 10:43 AM

 

Change to:
| Lo-Fi Version
0.0196sec    0.64    5 queries    GZIP Disabled
Time is now: 24th December 2025 - 08:17 AM