C Coding Competition - Win an Arduino

[Chet T16]

Firstly, I've asked Dave and he said it's fine to do this.

I have a little Arduino Pro Mini to give away to the winner of this coding competition. They're tiny and you could fit one anywhere!



To win the competition all you have to do is write the code which can find the first five "Perfect Numbers" in the fastest time.

From wikipedia:

In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself.

For example, the first perfect number is 6, as the factors of 6 (excluding itself) are 1, 2 and 3, and 1+2+3=6.

The first four numbers are:

6
28
496
8128

The fifth is a little bigger 

Rules:

• The code must be plain old C
• Only standard libraries to be used
• Numbers must be found based on the definition above i.e. by finding and adding factors only
• nything that runs for over an hour will be disqualified 

You can PM me your code and i will compile and run it on my machine, it's a bit slow so it may give a time greater than you measured but rest assured all code will be ran equally.

Closing date is undecided until i see what interest there is but i will give plenty of notice.

[RCMR]

You don't state the target system -- so are we to assume it's an Arduino?

[Chet T16]

I'll be compiling with gcc in cygwin. I think an arduino would crap itself!

[slateraptor]

To win the competition all you have to do is write the code which can find the first five "Perfect Numbers" in the fastest time.

The challenge states "find" rather than calculate...look-up tables count?

EDIT:

• Numbers must be found based on the definition above i.e. by finding and adding factors only

Not winning.

[adam1213]

somehow this sounds like a university assignment.

You could just directly print the numbers (solutions won't get much faster than this)

[slateraptor]

somehow this sounds like a university assignment.

More like a Project Euler puzzle with facebook puzzle caveats.

[slateraptor]

@Chet T16: PM sent.

P.S. Benchmarks as entries are tested would be nice.

[free_electron]

void main void{printf ("6\n28\n496\n8128\n33550336")};

you can keep the arduino. don't need it.

[nitro2k01]

• Numbers must be found based on the definition above i.e. by finding and adding factors only

This raises the question of what optimizations we're allowed to do, exactly. For example, are we allowed to check only every second number, under the assumption that all perfect numbers are even? (If odd perfect numbers exist, they're certainly much greater than the numbers relevant for this contest.) The current reading of that rule makes sure the programs are going to heat your room more than your brain. A more interesting rule, IMO, would be:

• Each number must be iterated and individually qualified according to known general mathematical properties of perfect numbers.

That way, the contest would actually be interesting.

[Mechatrommer]

next stop... the fastest sin(x) generator. prize = my "untested" PC display card backyard. winner pay shipping.
rule... no table lookup. memory consumption... less than 11 bytes.

[amyk]

• Numbers must be found based on the definition above i.e. by finding and adding factors only

This raises the question of what optimizations we're allowed to do, exactly. For example, are we allowed to check only every second number, under the assumption that all perfect numbers are even? (If odd perfect numbers exist, they're certainly much greater than the numbers relevant for this contest.) The current reading of that rule makes sure the programs are going to heat your room more than your brain. A more interesting rule, IMO, would be:

• Each number must be iterated and individually qualified according to known general mathematical properties of perfect numbers.

That way, the contest would actually be interesting.

The problem with competitions like this is that the output is known a priori and so a highly optimising compiler could replace the entire program with one output, as the program takes no external input. This would make all your attempted algorithmic optimisations useless, and in fact may confuse the optimiser so it no longer can produce that truly optimal solution. Programs that consume input, however, are much more interesting and that is why you'll see a lot of competitions like this one specify the expected output given a particular input.

[Chet T16]

OK, to clarify, the intention is to find the first five numbers by finding the factors and adding them up and checking the sum. The idea then is to find the best possible way of factorising large numbers as this is where 99.999% of the time goes.

This is based on a university assignment I had a few years ago while learning C, not something due now :p

[_Sin]

OK, to clarify, the intention is to find the first five numbers by finding the factors and adding them up and checking the sum. The idea then is to find the best possible way of factorising large numbers as this is where 99.999% of the time goes.

This is based on a university assignment I had a few years ago while learning C, not something due now :p

Why would you generate a number as a sum of factors, and then factorise it?

The following code ought to print out the first 8 perfect numbers with all factors, but it's not done the way you've asked so I guess it's not valid (and I'm not interested in the arduino anyway)

Code: [Select]

#include <stdio.h>
#include <math.h>

int isPrime(long long val)
{
int p,i;
if(val == 2) return 1;
if((val & 1) == 0) return 0;

p = (int) sqrt((float)val);
for(i = 3 ; i <= p ; i ++)
{
if((val % i) == 0) return 0;
}
return 1;
}

void main()
{
int i,j;
for(i = 2 ; i < 32 ; i++)
{
if(isPrime(i))
{
long long pn = (1 << i) - 1;
if(isPrime(pn))
{
printf("%lld\n", ((long long) (1 << (i - 1))) * pn);
for(j = 0 ; j < i; j ++)
{
printf("%d ", 1 << j);
}
for(j = 0 ; j < (i - 1); j ++)
{
printf("%lld ", (((long long)1) << j) * pn);
}
printf("\n\n");
}
}
}
}


[grumpydoc]

Here is an integer only solution which is fairly compact, though almost totally naïve in its approach.

Code: [Select]

include <stdio.h>
#include <limits.h>

void main(int argc, char *argv[])
{
  unsigned int p, f, t;

  for (p = 2; p < UINT_MAX; p += 2) {
    if (p == 6 || (p-1)/9*9 == (p-1)) {
      for (t = 0, f = 1; f*f <= p; f++) {
if (p/f*f == p) {
  t += f;
  if (p/f != f && f!=1) t += p/f;
}
      }
      if (t == p)
printf ("%d\n", p);
    }
  }
}

I'm not sure that it's a terribly interesting problem at the level of "print the first 6" though. I agree with the others who have pointed out that once you have exploited some property of perfect numbers such as "they're probably even"¹ to avoid factorising each positive integer summing the factors and checking to see if that equals the original number you might as well go for the printf("6\n28\n496\n8128\n33550336\n"); approach.

_Sin's code is actually more interesting, and much faster (Oh, BTW I don't want the Arduino either). It exploits the fact that 2^p-1(2^p-1) is an even perfect number if 2^p-1 is prime. the test for primeality in that code is a very simple one so, it's not as interesting as it could be.

If you want an interesting problem prove that 2^p-1(2^p-1) is perfect for p=25964951

[1] It has not been proven that there are no odd perfect numbers.

[Chet T16]

There are lots of properties of perfect numbers that can be exploited but thats not the idea, its about being able factorise and add all the numbers up to and including the last one - following the definition of a perfect number

[grumpydoc]

So the competition is about being able to write a fast factoriser.

Sorry, I'll do my own crypto cracking, not yours

It's still not interesting if you only want the first 5 or 6 perfect Nos.

[Chet T16]

So the competition is about being able to write a fast factoriser.

Sorry, I'll do my own crypto cracking, not yours

It's still not interesting if you only want the first 5 or 6 perfect Nos.

I'm sorry to disappoint but the competition is all i say it is, no other motives. I thought it might be nice to have something different than the threads that descend into negativity that have become so common on here lately but it looks likes that's failed!

[SeanB]

Nice idea, nice to do, and I would enter if I could code better than a dyslexic gibbon let loose on a keyboard.............

Oh wait, That is me all the time I think.

[slateraptor]

I'm sorry to disappoint but the competition is all i say it is, no other motives. I thought it might be nice to have something different than the threads that descend into negativity that have become so common on here lately but it looks likes that's failed!

Well, I guess I'll be going back to Project Euler to get my coding challenge fix...a shame, really.

[Chet T16]

If you want something interesting I have a program that takes a 4 digit input (numbers and letters) and outputs a 4 digit code (numbers only) that I would like to reverse engineer

[Chet T16]

Oh and regarding the challenge this is obviously aimed at people who only have a little experience coding. People like me!

[_Sin]

I wasn't trying to be negative, I just went off on a tangent and thought someone might be interested...

[slateraptor]

If you want something interesting I have a program that takes a 4 digit input (numbers and letters) and outputs a 4 digit code (numbers only) that I would like to reverse engineer

Roughly 15 million input permutations mapped to 10k possible outputs...brute forcing a reverse engineered sol'n would be trivial.

[Chet T16]

Roughly 15 million input permutations mapped to 10k possible outputs...brute forcing a reverse engineered sol'n would be trivial.

Is that an offer? :p

[grumpydoc]

I wasn't trying to be negative, I just went off on a tangent and thought someone might be interested...

Which I thought to be perfectly valid, it's much more efficient to generate perfect numbers from Mersenne primes than by factorising each positive integer. Even if you replace the "computing 101" factorisation algorithm from the code I posted with a more efficient one it will still be slower than yours at generating perfect numbers.

Yours can still be improved though as your primeality test is fairly simplistic - perhaps by dividing by primes less than the square root of the number of interest, rather than potentially by all integers >= 3. Or even just dividing by odd numbers.

Chet T16 - the code I posted was intentionally a bit simplistic but if you are a beginner in C programming it is probably worth making sure you understand it, then make sure you understand _Sin's. Then see if you can spot the (obviously deliberate ) errors of coding style in both - there are things in _Sin's that I would reject at code review. There again there are things in mine that I would also question now that I re-read it. No-one's perfect!!

[slateraptor]

...it's much more efficient to generate perfect numbers from Mersenne primes than by factorising each positive integer.

*giggles*

Is that an offer? :p

I'm tempted to say sure for shits and grins...but I think I'll pass. I wouldn't want to spoil a good learning opportunity.

[_Sin]

Yours can still be improved though as your primeality test is fairly simplistic - perhaps by dividing by primes less than the square root of the number of interest, rather than potentially by all integers >= 3. Or even just dividing by odd numbers.

Chet T16 - the code I posted was intentionally a bit simplistic but if you are a beginner in C programming it is probably worth making sure you understand it, then make sure you understand _Sin's. Then see if you can spot the (obviously deliberate ) errors of coding style in both - there are things in _Sin's that I would reject at code review. There again there are things in mine that I would also question now that I re-read it. No-one's perfect!!

Yes, I put in a mostly trivial primality test with the intention of replacing it with something a bit faster after proving that the code worked, but as it generates all the perfect numbers <64bits long without any appreciable time delay, it seemed pointless to optimise further.

I think minor optimisations on the primality test wouldn't get very far, however. To test only primes there would need to either be a rather large table, or a recursive call to the prime test (which is significantly slower than brute force in this instance). I did originally generate the primes, but the memory requirements shoot up beyond (IIRC) the 5th perfect number and it started to take noticeable amounts of time to generate.

Considering that only a tiny handful of potential primes are ever even considered in the code, it seemed that a simple test would be a far better option than trying to generate/store primes. Unless I stored only the primes I know I'd need, but then I might as well just store the answer, and that seemed like cheating.

I had a simple implementation of miller-rabin, which is probabilistic (but known good over the range required here). However it seems unnecessary speed-wise, and would have complicated the code.

And no, I wouldn't want anyone taking that code as a good example of anything

[grumpydoc]

Good points.

It's worth remembering that in the real world "good enough" is often just that - "good enough". I think your observations about minimal gain are very valid. One shouldn't optimise unless the section of code in question has shown to be an important bottleneck - and one shouldn't optimise implementation before optimising the (choice of) algorithm.

Another important point that you touch upon is that it's sometimes necessary to trade memory use for speed, or vice versa depending on resources. This is especially true for embedded systems. Another thing is that sometimes an approach which should be faster in theory turns out not to be so in practice as you found with storing primes.

Finally remember that there is a sometimes a trade off between efficiency and maintainability - miller-rabin will be faster but if the next person to maintain the code hasn't a clue how it works it might not be such a good idea.

See - you can make any bit of programming interesting as long as you don't constrain it too much.

[DavidJRobertson]

My working but inefficient solution:

Code: [Select]

#include <stdio.h>

void main() {
  int i = 2;
  int numfound = 0;
  int factorsum;
  int j;
  int hold[1000000]; // Probably doesn't need to be this big but whatever...
  int cv;
 
  while (numfound < 6) {
    factorsum = 1;
    for (j = 2; j < i; j++){
      if (i % j == 0) {
        if (hold[j] == 0) {
          factorsum +=j;
          hold[j] = 1;
        }
        if (hold[i/j] == 0){
          factorsum += i/j;
          hold[i/j] = 1;
        }
      }
    }
   
    if (factorsum == i) {
      printf("%10d\n", i);
      numfound++;
    }
   
    for (cv = 0; cv < 100000; cv++) {
      hold[cv] = 0; 
    }
   
    i += 2; // Assuming all answers will be even
  }
}


[westfw]

find the best possible way of factorising large numbers

A "known to be hard" problem.  Though the 5th perfect number hardly qualifies as "large."
There are probably lots of published algorithms, although they tend to be aimed at finding "prime factors."  (A list of prime factors gives you all of the factors pretty easily, though.  I think.)

I think you should require that it actually run on an Arduino.  The relative lack of RAM might add an interesting component to the challenge...