response 1 of 32:

Feb 19 20:47 UTC 2000

I'm a big fan of Raymond Smullyan's logic puzzles.  I've been working through 
one of his recent books, called "The Riddle of Scheherazade".  The premise is 
that after the 1001st night, Scheherazade went on to tell the king puzzles for 
several subsequent nights.  On the thousand and thirteenth night, she gets to 
this one:

A certain prince Al-Khizr was in love with the sultan's daughter and asked for 
her hand in marriage.

"My daughter is very choosy," said the sultan, "and wants to marry only 
someone who shows extraordinary intelligence.  So if you want to marry her, 
you must first pass eight tests."

"What are the tests?" asked the suitor.

"Well, for the first test, you have to write down a number that will be sent 
to the princess.  She will then send back a number to you.  If she sends back 
the very same number that you have sent her, then she will allow you to take 
the second test.  But if her number is different from yours, then you are 
out."

"Now, how can I possibly know what number to write?" asked the suitor.  "How 
can I guess what number the princess has in mind?"

"Oh, she doesn't have a number in mind," said the sultan.  "The number she 
sends back is dependent on the number you send.  The number you send 
*completely determines* what number she will send back.  And if you send the 
right number, she will send back the same number."

"Then how can I guess the right number?" asked the suitor.

"It's not a matter of *guessing*," said the sultan.  You must *deduce* the 
correct number from the rules I am about to give you.  For any numbers x and 
y, by xy I mean not x *times* y but x *followed by* y, both numbers, of 
course, written in base 10 Arabic notation.  For example, if x is 5079 and y 
is 863, then by xy I mean 5079863.  Now here are the rules:

Rule 1: For any number x, if you send her 1x2, then she will send you back the 
number x.  For example, if you write 13542, she will write back 354.

Rule 2: For any number x, the *repeat* of x means xx.  For example, the repeat 
of 692 is 692692.  And now, the second rule is that if x brings back y, then 
3x will bring back the repeat of y.  For example, since 15432 brings back 543, 
then 315432 will bring back 543543.  From which it further follows that if you 
send her 3315432, you will get back 543543543543 (since 315432 brings back 
543543).

Rule 3: The *reverse* of a number means the number written backwards.  For 
example, the reverse of 62985 is 58926.  The third rule is that if x brings 
back y, then 4x brings back the reverse of y.  For example, since 172962 
brings back 7296, then 4172962 brings back 6927.  Thus, if you send her the 
number 4172962, you will get back 6927.  Or, combining Rules 1, 2, and 3, 
since 316982 brings back 698698 (by Rules 1 and 2), then 4316982 brings back 
896896.

Rule 4 (The Erasure rule):  If x brings back y, and if y contains at least 2 
digits, then 5x brings back the result of erasing the first digit of y.  For 
example, since 13472 brings back 347, then 513472 brings back 47.

Rule 5 (The Addition Rule):  If x brings back y, then 6x brings back 1y and 7x 
brings back 2y.  For example, since 15832 brings back 583, then 615832 brings 
back 1583, and 715832 brings back 2583.

"Those are the rules," said the sultan, "and from them can be deduced a number 
x that will bring back the very number x.  There are actually an infinite 
number of solutions, but any single one will suffice for passing the first 
test."

"Are there any *meanings* to these numbers?" asked the suitor.

"Ah, that is the princess' secret, but fortunately you don't have to know the 
meaning in order to pass the first test."

response 3 of 32:

Feb 21 22:41 UTC 2000

OK, here are some hints.  Clearly every valid input looks like this:

x1y2

where x is a sequence of digits taken from { 3,4,5,6,7 }, and y is any string
of digits.  You can think of starting with 1y2, and then tacking digits on
to the beginning until you get what you want for output.  Note that if
  d = length of input - length of output
then d starts out at 2.  Tacking on a 4 increases d by 1, a 5 increases it
by 2, and a 6 or a 7 leaves it unchanged.  So the only way to decrease d is
by tacking on a 3.  Since d starts out at 2 and you want it to be 0, it
follows that you need to use at least one 3.

response 5 of 32:

Feb 24 17:28 UTC 2000

OK, here's a "sub-puzzle":  If x yields y, what prefix p can you add to x so
that px yields y2 ?

response 7 of 32:

Feb 24 19:25 UTC 2000

 x -> y  ==> 474x -> y2   in these rules.

I've been conjecturing that it is likely that all of the rules are used 
at least once in the solution, simply because it's a manufactured 
problem.  I think I have some ideas about how prefixes 3, 4, and 7 get 
used, as well as 1 and 2, but I haven't really been able to get good 
ideas about 5 and 6 yet.  

response 9 of 32:

Feb 24 19:52 UTC 2000

Re #6,7: Flem is correct.  A string that begins with 2 would not be valid
input.

Re #7: Remember that there are 8 tests, so if you don't use all the rules on
the first one, you will get more chances to use them later.

Re #8: That's correct.  How do you know that, Paul?

OK, now that Greg has told us that x -> y implies 474x -> y2, what prefix q
could you add to x so that qx -> yy2 ?

response 11 of 32:

Feb 24 22:22 UTC 2000

Oh, I was under the impression that this particular set of rules applied 
only to the first test.  

response 13 of 32:

Feb 25 15:40 UTC 2000

Ah, I see...

response 15 of 32:

Feb 26 21:05 UTC 2000

I'll do the deed.

47431x2 -> xx2, so substituting 47431 for x, we get
  47431474312 -> 47431474312

response 19 of 32:

Feb 28 14:58 UTC 2000

For the third test, the suitor had to send the princess a number x such that
she would send back the reverse of x.  What number x would work?  An extra
bonus would be given if the number x contains no more than 12 digits.