640 - Self Numbers

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by Ryan Pai » Fri Aug 27, 2004 10:23 am

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

Post by Arm.Turbo » Fri Aug 27, 2004 12:18 pm

Thx Ryan Pai
I AC now.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

Post by wolf » Thu Sep 02, 2004 10:10 pm

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

Post by oldbam » Mon Oct 18, 2004 11:09 pm

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

Post by Ivor » Fri Oct 22, 2004 8:59 pm

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

Post by akhter900 » Thu Nov 25, 2004 12:42 pm

++++++++++++++++++++++++++++++++++++

:P O YES,

:wink: THANKS A LOT.
&
:cry: 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:

Faster I/O please

Post by I LIKE GN » Sat Mar 12, 2005 2:57 pm

How can I generate FASTER I/O :oops:
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:

Post by Lord Nemrod » Tue Mar 29, 2005 9:47 pm

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? :-?

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Apr 06, 2005 1:56 am

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:

Post by Lord Nemrod » Wed Apr 20, 2005 8:53 am

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

Post by mohsincsedu » Sun Nov 20, 2005 6:19 pm

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



Thanks in advence!!!
Amra korbo joy akhdin............................

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Mon Nov 21, 2005 9:25 pm

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?

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

selfnumbers

Post by jagadeesh » Sun Oct 22, 2006 9:00 pm

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

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

self numbers

Post by jagadeesh » Sun Oct 22, 2006 9:16 pm

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
hope u all will reply
and being new i need to know how to discuss these in this group
thanking u
jagadeesh

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Mon May 07, 2007 8:43 am

could any one say his algorithm to generate fast
sorry for my bad english!!

my time is 0.389

Post Reply

Return to “Volume 6 (600-699)”