## 10042 - Smith Numbers

Moderator: Board moderators

zprian
New poster
Posts: 13
Joined: Wed Mar 09, 2005 1:16 am
HI WR!! I OBTAINED AN ACCEPT!!!jejeje
I change the loop, and I check each number and use long, and now my program is ACCEPT!!!
thanks very much for all!!!

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### ACC 10042 ..At last

Thanks For I/O
I Got ACC Now.I forgot To Post

Thank's

Rocky asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10042

Hello can anybody plz help me to understand the problem 10042? Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
At first make sure what a smith number is. By definition - Smith number is such a number that the sum of its digits is equal to the sum of digits of all it's prime factors (considering frequency). Let's consider the example given in the problem.
4937775 can be written as 3 * 5 * 5 * 65837 - which are it's prime factors.
Now, if you sum the digits of the original number, you get (4 + 9 + 3 + 7 + 7 + 7 + 5) = 42. Again summing the digits of the prime factors leads to -> {(3) + (5) + (5) + (6 + 5 + 8 + 3 + 7)} = 42. As both the sums are equal, 4937775 is a smith number.

Now, if you check the sample input, you will find 4937774 is not a smith number. Increment the number by one until you get a smith number which is the immediate next one in this case.

Similarly, if the input is 105, it's not a smith number and 106,107,108....,120 - none of these are smith #. The first smith # after 105 is 121. This will be your output. Hope it helps. You should never take more than you give in the circle of life.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### Thanks

Thanks Mahmudur Bhai for your help.I now understand the problem and get ready for code.

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

### 10042 WA

Hello!

I have problems with my program . Can anybody tell me what's wrong in the code. I use algorithm from Programming Challenges.

Code: Select all

``````// 10042: Smith numbers

#include <cmath>
#include <iostream>
using namespace std;

typedef unsigned long inte;

inte sum (inte n)
{
inte r = 0;
while (n)
{
r += n % 10;
n /= 10;
}
return 0;
}

// This algorithm is from Programming challenges,
// it works for me in other ACM problems
inte ptr (inte w)
{
inte n = w;
inte rez = 0;

while (n % 2 == 0)
{
rez += 2;
n /= 2;
}

inte i = 3;
while (i <= (sqrt(n) + 1))
{
if (n % i == 0)
{
rez += sum(i);
n /= i;
}
else i += 2;
}

if (n > 1) rez += sum(n);

// If n == w ==> n is prime
if (n == w) return false;

if (sum(w) == rez) return true;
return false;
}

int main (void)
{
inte t; cin >> t;

while (t--)
{
inte n; cin >> n;
while (!ptr(++n));
cout << n << endl;
}

//	system("pause");
return 0;
}

``````

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
You made a very careless mistake in your code. I refer you to this part of your code:

Code: Select all

``````inte sum (inte n)
{
inte r = 0;
while (n)
{
r += n % 10;
n /= 10;
}
return 0;
}
``````
This sum function is always returning 0. I think you meant return r.

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:
chunyi81, thank you very much, i've got AC.
I don't even think that my mistake is so obivious  Thank you once more Masud
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Contact:

### 10042

I dont know why judge give me wrong answer
My code is given below...
What is the problem of it...

Code: Select all

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

long long int DigSum(long long int t)
{
long long int m=0;
while(t)
{
m+=t%10;
t/=10;
}
return m;
}

long long int PrimeFactorSum(long long int t)
{
long long int k=0,i,d;
while(t%2==0)
{
k+=2;
t/=2;
}
d=sqrt(t);
for(i=3;i<=d;i+=2)
{
if(t%i==0)
{
while(t%i==0)
{
k+=DigSum(i);
t/=i;
}
d=sqrt(t);
}
}
if(t>=i)k+=DigSum(t);
return k;
}

void main()
{
long cas;
long long int sum1,sum2,n;
scanf("%ld",&cas);
while(cas--)
{
scanf("%lld",&n);
while(0==0)
{
sum1=DigSum(n);
sum2=PrimeFactorSum(n);
if(sum1==sum2)break;
else n++;
}
printf("%lld\n",n);

}
}
``````
Hi I am Masud...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
For every input value n, you are to compute the smallest Smith number which is larger than n.
...prime number is not worth being a Smith number...
Always search the forum for existing threads about your topic and use them if necessary instead of creating a new one. I'm sure you'll find a lot more help along with some test I/O if you search.

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain

hi,

in 10042 smith numbers, i try the all input from other topic and get correct answer use gcc.

but when i submit my code, it gets signal 11 (SIGSEGV). Meaning:
Invalid memory reference

but i don't know in what condition could make this mistake

is there anyone can help me? thx.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
It is possibly because of your program tried to access the invalid memory, for example if you write the code like this :

Code: Select all

``````int arr;
arr = 5;
printf("%d\n",arr);
``````
It might be error, because you made an array with capacity only 1000 but you tried to access the 1002nd array... (0 is the 1st array).

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain
if my array is : int prime; and i write a function
int digitsum(unsigned long int a)

then i write
psum+=digitsum(prime);
could make SIGSEGV ?

or unsigned long int s
but s=s%prime or s/=prime
could make SIGSEGV ?

because i test all data from 0 - 10^9 in gcc and all answer is fine

but when i submit... get SIGSEGV

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
Maybe its time you posted the code in its entirety.
--
Suman
My Blog
My Web Page

rieo
New poster
Posts: 9
Joined: Tue Jul 04, 2006 10:46 am
Location: Taiwain
finally i get accept, i found the bug is i use store primes which are <100000
, and when i test the input s, and use s to mod by prime.. if use all the primes < 100000, s still can't be 1, i wrote if (s>prime) digitsum(s)
and get RE

when i change the code to if (s!=1) the digitsum(s) directly... it's accept