## 640 - Self Numbers

Moderator: Board moderators

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
Close.

All of those numbers are self-numbers, but you're missing one.
I'm always willing to help, if you do the same.

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm
Thx Ryan Pai
I AC now.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Hi all !
I wrote a program, which solvs the problem, but runing sth about 50 sec on my computer !!! How to make it faster ?

[cpp]
#include <iostream>
#include <conio.h>

using namespace std;

int sum_of_digits(long n)
{
long k,power;
int sum;
for (power=1;;power*=10)
{
if (n/power==0) break;
}
power/=10;
for (k=power;k>1;k/=10)
{
sum+=n/k;
n%=k;
}
sum+=n;
return sum;
}

int isself(long l)
{
long j,temp;
for (j=l-1;;j--)
{
temp=sum_of_digits(j);
if (temp+j==l) return 0;
if (temp+j<l) return 1;
}
}

int main()
{
for (long i=1;i<=1000000;)
{
if (isself(i)==1)
{
cout << i << endl;
}
if (i+2%2!=0)
{
if (isself(i+2)==1) i+=2; else i+=11;
}
else i+=11;
}
return 0;
}
[/cpp]

oldbam
New poster
Posts: 17
Joined: Tue Sep 14, 2004 9:30 am

### 640

Hi! I saw that some guys solved 640 in 0.00 or something like that. Is it possible to find such a quick algorithm or they just did precalculation?
Life is beautifull !!!

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
It isn't possible to solve this in 0.000 at all. The time I have is the result of the glitch in the system some two years ago. Else I would have time around 0.010-0.020. That is a possible time. With good IO and a trick to generation of the numbers.

Cheers,
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

akhter900
New poster
Posts: 7
Joined: Fri Mar 19, 2004 3:27 pm
++++++++++++++++++++++++++++++++++++

O YES,

THANKS A LOT.
&
SORRY FOR LATE THANKS.

++++++++++++++++++++++++++++++++++++
AkHtEr

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

How can I generate FASTER I/O
Mine is 0:00.391
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:
Dear Cyfra.
I have actually solved the problem the way you are advising to do, and it does generate all self numbers, but it takes around 5 minutes to do it? Any better suggesstions?

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
A better approach could be to first pre-calculate all self-numbers
from 1 to 1000000 using a technique similar to the
Eratosthenes Sieve ( although the logical checks in the algorithm
and actually the whole logic are quite different ).

Then, as a second step, you just loop and print the self-numbers.

Please let me know if you need more details.

P.A.Petrov ( Sedefcho )

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:
Well, in fact I DO need details:) if you would be so kind to provide any...
Thx

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### 640 TLE

Hi All.............................

Plz tell me efficient Algorithm.

I got TLE.

Here is my code:

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 1000000

char table[MAX+2];

long long sumdigit(long long n)
{
long long sum = 0;
while(n>0)
{
sum+=(n%10);
n/=10;
}
return sum;
}

void unself(long long n)
{
long long i, sum;
i = n;
while(i<=MAX)
{
sum = sumdigit(i);
i+=sum;
//if(i<=MAX)
table[i] = '1';

}
}

void main()
{
long long i;
memset(table,'0',MAX);

for(i = 1;i<=MAX;i++)
{
if(table[i]=='0')
{
printf("%lld\n",i);
unself(i);
}
}

}``````

Pls help me!!!!!!!

Amra korbo joy akhdin............................

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
hmm...

Well there is no reason why ur code should NOT get TLE. you are running a code with a complexity of O(1000000*1000000).

Your problem is in the unself part. You dont have to generate the whole sequence ... just cut off the number that can be generated by the current number i.e. 'n'.
Where's the "Any" key?

New poster
Posts: 3
Joined: Sun Oct 22, 2006 8:04 pm

### selfnumbers

dear
i am new to this group
one of my student has derived a formulae to generate self numbers
that tooat the age of 16
it was approved by the cochin university
and he was congratulated by his highness the president of india
i am a mathematics teacher
i want to discuss this
and to introduce the boy to this group
kindly inform what to do

New poster
Posts: 3
Joined: Sun Oct 22, 2006 8:04 pm

### self numbers

dears
i am new to this group
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by the cochin university of acience and technology
and he was congratulated by his highness the president of india
he has proved googol is not a self number
and generated a formulae for this
he named the largest he found on his name
and that is 10*10^1000000
he had such immense intuition that he will deliver in seconds whether a number is a self number or not
i like to discuss this matter and like to introduce the boy to the group
i am a mathematics teacher who was working in trk higher secondary school in india
and now in mes indian school qatar