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!!