1. Member
Join Date
Apr 2009
Posts
3
Rep Power
0

## Entire problem

Hello..

Yes, this thread is only part of the problem.

The entire problem is:

We must find the 12nd number that

original number *8/3 = number modified(1234 -->4123);

INCORRECT EXAMPLE : 1234 * 8 /3 = 4123 --> 1234*8/3 != 4123
CORRECT EXAMPLE: : 27 * 8 / 3 = 72

See the entire search for the 12nd number:
1. Original number: 27 - Modified number: 72
2. Original number: 2727 - Modified number: 72
3. Original number: 116883 - Modified number: 311688
4. Original number: 155844 - Modified number: 415584
5. Original number: 194805 - Modified number: 519480
6. Original number: 233766 - Modified number: 623376
7. Original number: 272727 - Modified number: 727272
8. Original number: 311688 - Modified number: 831168
9. Original number: 350649 - Modified number: 935064
10. Original number: 27272727 - Modified number: 72727272
11. Original number: 2727272727 - Modified number: 7272727272
12. Original number: 116883116883 - Modified number: 311688311688

We need to create a efficient algorithm, althoug the problem will spend hours to find the 12nd number. And, thats why using only integers besides using String.

Does anyone knows an efficient way to do this search? Thx everybody for ur participation!!!

2. Member
Join Date
Apr 2009
Posts
3
Rep Power
0
Hello..

Yes, this thread is only part of the problem.

The entire problem is:

We must find the 12nd number that

original number *8/3 = number modified(1234 -->4123);

INCORRECT EXAMPLE : 1234 * 8 /3 = 4123 --> 1234*8/3 != 4123
CORRECT EXAMPLE: : 27 * 8 / 3 = 72

See the entire search for the 12nd number:
1. Original number: 27 - Modified number: 72
2. Original number: 2727 - Modified number: 72
3. Original number: 116883 - Modified number: 311688
4. Original number: 155844 - Modified number: 415584
5. Original number: 194805 - Modified number: 519480
6. Original number: 233766 - Modified number: 623376
7. Original number: 272727 - Modified number: 727272
8. Original number: 311688 - Modified number: 831168
9. Original number: 350649 - Modified number: 935064
10. Original number: 27272727 - Modified number: 72727272
11. Original number: 2727272727 - Modified number: 7272727272
12. Original number: 116883116883 - Modified number: 311688311688

We need to create a efficient algorithm, althoug the problem will spend hours to find the 12nd number. And, thats why using only integers besides using String.

Does anyone knows an efficient way to do this search? Thx everybody for ur participation!!!

3. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,565
Rep Power
12
Just a small point: 116883116883 is somewhat large to be dealt with using int variables. If you are allowed to use them, use long. (Of course, some might regard it as an "intellectual question" how to use int...)

Personally, I'd wonder if a little number theory might arrive at a solution faster than computation. Or at any rate suggest speedups. But I won't wonder that in any detail for fear of offending against OrangeDog's injunction not to criticise. So, go at it with brute force and grim determination: and call that an "interesting intellectual question".

4. The question doesn't say you have to use brute force and grim determination. Finding a better way to do it is indeed an "interesting intellectual question". I have other things to be getting on with myself or I would do the whole thing for funsies.

Hint: there's a clear pattern involving the combinations 27 and 116(883). Does 155844155844 satisfy the condition?
Last edited by OrangeDog; 04-20-2009 at 03:39 AM.

5. Member
Join Date
Apr 2009
Posts
49
Rep Power
0

## Re Invert Integer

hey mate,

well this is much more difficult than the original problem posted.

Just before I begin the mathematics, I want to be 100% clear that you seek to find a integer n such that

n x ( 8 / 3) = reversed(n)

if n does not have to be an integer, the simple solution is

n = (3 / 8) * reversed(n)

although I doubt it would be that simple.

Okay, first off let m = reversed(n) --> n = reversed(m) (or lets impose)

then our expression becomes,

reversed(m) = m x ( 8 / 3)

given m is an integer, then we know 8*m is an integer, however to ensure (8 *m) / 3 is definately an integer we must ensure that
8*m = 8*(3k) ; k being any integer ( i.e. it is divisible by 3 )
There are many forms in which we may put 8*m to ensure its divisible by 3, however one of the simplest forms would be
8 *m = 8 * k * (k + 1) * (k + 2) for all integers k.
and mainly
m = k^3 + 3*k^2 + 2*k

This unfortunately is only 1/100 th of the problem,

given m would yield a number of the form (impose order p)

m = k^3 + 2*k^2 + 2*k = sum ( a(i) * 10^(i) , i = 0 to p)
whereby a(i) are O(1) integers (i.e. single digits)
then we need to solve k, such that
8 * ( k^3 + 2*k^2 + 2*k) = reversed(m)
As reversed(m) has the same order we arrive at
8 * (k^3 + 2*k^2 + 2*k) = sum( a(p - i) * 10^(i) )

hmmmm, I can't say I would know a definative way of attacking this head on however, if you where to impose a brute force technique, the following may work,

private static int find_reverse_int(){
int k = 1; // k = 0 holds
int temp;
count = 1;
while (count <= 12){

temp = 8 * (k^3 + 2*k^2 + 2*k) //evaluate the powers using the Math.pow method - however make sure to cast back to an int

if(temp/3 == reversed(temp)){
count++
}

k++;

}
return temp;
}

whereby reversed(temp) can be achieved using the techniques provided already. The only hesitation I would have with this is the infinate loop this may create, however you have shown certain values that do work.

Hope this helps,

David

ps - I will have a look at this in more detail tonight and hopefully will be able to provide a more substantial algorithm ( I know what I've provided is weak at best!)
Last edited by DavidG24; 04-21-2009 at 10:49 AM.

6. Interesting indeed... I've done some digging on google and came across this page: Nabble - java.net - soujava java-list - [Desavio] Algoritimo pouco eficiente.
Its in Portuguese and here's the OP by using google trans:
Oops,
I'm doing the chair Complexity of Algorithm, and I'm breaking my head to solve a challenge of the teacher quickly.
The algorithm must find the twelfth number that the connection algorithm described below:
The algorithm can have only integer variables (int, long ...)
Take the last digit of the number and goes to front, example 12345 becomes 51,234
is multiplied by 8 / 3 and this number must be the same as the number of entry, example 51,234 multiplied by the 8 / 3 to be considered by the algorithm should result 12345.

* The MMC of 8 / 3 is 24, so the meter can be done in 24 in 24.

Problem:
* The program is taking over an hour to find the seventh number.

My code then attached: TestIntPalindromo.java

Who has some idea of how to improve means this algorithm.

There's a solution posted similar to David's above, but the concluding posts towards the end seems to mark this problem as NP-Complete.

Linear programming - Wikipedia, the free encyclopedia
P = NP problem - Wikipedia, the free encyclopedia

7. Member
Join Date
Apr 2009
Location
Brisbane
Posts
86
Rep Power
0
Originally Posted by OrangeDog
You can do it in place using either a single temp char variable or using XORs to swap the values.
Huh XOR? Let's see... 'A'==41 XOR 'B'==42
Java Code:
```    101001
XOR 101010
=   000011 = 3```
Nope I'm definately missing something. Care to clue me in? Please?

8. to swap x and y:
Java Code:
```y = x ^ y;
x = x ^ y;
y = x ^ y;```
Though it's much easier to see what you're doing if you use a temporary variable. You'd mostly use this when programming in assembler with limited number of registers.

This works because XOR is a self-inverting operation. For any x, x^x = 0 and x^0 = x. Therefore x^y^x = y.
Last edited by OrangeDog; 04-20-2009 at 04:11 PM.

Page 2 of 2 First 12

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•