Please, recommend readers some manual with good opcode reference.

1. Flags effected by instructions: EFLAGS Reference. (Volume 1, Appendix A)

2. Instruction Encodings. (Volume 2, Appendix B)

I also have a very nice periodic table of the elements on the wall.

**iblis**, you are correct - talk is the best we have. :) Have you also thought of sequences like: 7A FF C8 ?? ?? I was also trying to find a method with two Jcc. There seems to be many complex opportunities, but we could systematically rule them out - it would just take time, imo. Also, we should ask the question: in what state must the CPU be in after the five bytes - are we allowed to destroy the stack/registers/etc? Do the bytes have to be contigious in memory? Does execution even have to continue after the five bytes? Not that this will help us on this problem specifically, but there are others.

Have you also thought of sequences like: 7A FF C8 ?? ??

Very interesting. But what happens if PF = 0?

```
[size=12] If PF == 1 If PF == 0
```

.----------. .-----------------.

| jpe $+1 | | jpe $+1 |

| / | | / |

| dec eax | | enter ?? ?? ?? |

| ?? ?? | | |

----------' -----------------'[/size]

The PF=0 scenario leads to an enter with 3 bytes of operands and exceeds the 5 byte limit. But I understand your point. There might be some very strange solution out there that normally we couldn't possibly hope to figure out unless we stumbled upon it by accident or brute forced it.

I was also trying to find a method with two Jcc. There seems to be many complex opportunities, but we could systematically rule them out - it would just take time, imo.

I was fiddling with 2 Jccs also awhile back but didn't find anything useful. 2 Jcc's would require 4 bytes unless they overlapped, but all of the Jcc opcodes I see don't allow for overlapping because the opcodes, ranging from 70h - E3h, would jump us out of bounds. (Unless we're allowed to scatter the code - but I don't know if that's allowed. TheSvin could tell you since he invented the question.) You could also maybe overlap one or more of the Jccs with some other opcodes, but it's too late in the day to dedicate my brain to that kind of stress. ;)

Also, we should ask the question: in what state must the CPU be in after the five bytes

Good question. I imagine the post-state can be anything since TheSvin didn't specify. The only state we need is eax/ax = -1. Although with regards to practicality, any stable or correctable state would be preferrable. I think a more important question would be

*what state should the CPU be in*For example, if the state of the carry flag is always 1, then the problem is solved. ;)

**before**the five bytes?But based on the simplicity of the question, intuition tells me that the pre-state can be anything. We can't rely on any potentially volatile circumstances to be constant.

are we allowed to destroy the stack/registers/etc? Do the bytes have to be contigious in memory? Does execution even have to continue after the five bytes? Not that this will help us on this problem specifically, but there are others.

Again, the person to answer that would be TheSvin, since he invented the question. Although I doubt he gave any thought to any of that when he asked it. I still think that '5' was a typo or a miscalculation on his part. Either that or he was biting off more than he could chew. Getting him to admit to it is another matter. ;)

I personally would like to see it done with 5 contiguous bytes using nothing other than EAX for storage. But in fact that is the scenario that I think is impossible. Having it done another way would still be very impressive to see though. --The best solution? Have a mod edit TheSvin's post and replace the '5' with '6'. :grin:

Getting him to admit to it is another matter.

Oh I's no problem, I could admit anything :)

I've proved it before.

The thing is that I don't want to do it right now,

'cause the more I remain silence the more productive stuff I can see from other part in discussion.

Prove me wrong or find solution. That's what I'd say for now.

Despite that the solution hasn't been found, many interesting thought have been shown in discussion about it. So you can call me any name - I still think that discussion is getting more and more usefull for everybody

and I'm not going to finish it :)

You see we just start real analyze here.

We need enumarate all possible short ways to fill reg16 and reg32 with bits.

Give clear sceme on code overlap triks etc. etc.

I didn't say if I had solution or I didn't have it.

But I promisse to say it if you prove that it is impossiple

:)

Prove it! I enjoy the way you think :)

So far I only know of a few operations that can be used to check the status of the parity flag

You forgot of cmovcc option. Might be used with 66 prefix.

Also among other way to set bits there are

stack method (also can be used with 66)

About the CMOV one, I had thought about it but I quickly leaded it out because it doesn't work on Pentiums, and AFAIK you work on a Pentium, so I doubt++ you wanted a CMOV solution. Also, it doesn't seem suitable for <=5 bytes solution, at least at a first analysis.

Stack is cool.. I thought too about some PUSHF tricks (just like the LAHF I mentioned), but in general the 5 bytes requirement make it look tough.

Stack is cool.. I thought too about some PUSHF tricks (just like the LAHF I mentioned), but in general the 5 bytes requirement make it look tough.

Example:

Question

Is it possible to have a number

(n+1)^2

that have sum of digits = (n-1)/2

```
xor ecx, ecx ; (n+1)
```

sub esp, 16

_0:

mov eax, ecx

mul ecx ; (n+1)^2

mov [esp+4], edx

mov [esp],eax

fild qword [esp]

fbstp [esp]

; sum digits

mov eax, [esp]

mov edx, eax

shr eax, 4

and edx, 0F0F0F0Fh

and eax, 0F0F0F0Fh

imul edx, 01010101h

imul eax, 01010101h

add edx, eax

mov eax, [esp+4]

mov ebx, eax

shr eax, 4

and ebx, 0F0F0F0Fh

and eax, 0F0F0F0Fh

imul ebx, 01010101h

imul eax, 01010101h

add eax, ebx

add eax, edx

shr eax, 24

; compare to (n-1)/2; ECX = (n+1)

lea eax, [eax*2 + 2]

sub eax, ecx

je _x

inc ecx

jns _0

or eax, -1

_x:

add esp, 16

I know it's messy, but it was the least effort. ;)bitRAKE, looks good. I think The Svin wanted a more analytical approach.

Look at the problem this way:

let f(n) = (n+1)^2

and

let g(n) = (n-1)/2

The max number of digits f(n) can be for any given n is: floor( log_10( f(n) ) + 1 )

So the maximum value for the digit sum of any given n is: floor( log_10( f(n) ) + 1 )

let h(n) = ( log_10( f(n) ) + 1 ) * 9

So to narrow down the amount of whole positive integers you'll need to test, you want to find a value of

(n-1)/2 = ( log_10( (n+1)^2 ) + 1 ) * 9

Instead of doing the math, it's faster to graph it out. If you graph h(n) and g(n) you'll see that g(n) surpases h(n) at approximately n = 74.

So armed with this, and a list of all n's for n < 74, you can prove that it is impossible. ;) And it saves a lot of work and explanation.

This is the kind of method I think TheSvin wanted to try with the "if PF = 1 eax = -1 else ax = -1" challenge. But I don't exactly know how to begin adapting mathematical theory to a 5 byte algorithm. <scratches head>

It's interesting though.

Look at the problem this way:

let f(n) = (n+1)^2

and

let g(n) = (n-1)/2

The max number of digits f(n) can be for any given n is: floor( log_10( f(n) ) + 1 )

So the maximum value for the digit sum of any given n is: floor( log_10( f(n) ) + 1 )

*** 9**let h(n) = ( log_10( f(n) ) + 1 ) * 9

So to narrow down the amount of whole positive integers you'll need to test, you want to find a value of

*n*such that g(n) > h(n). So to find n you have to write it out as an equality and solve:(n-1)/2 = ( log_10( (n+1)^2 ) + 1 ) * 9

Instead of doing the math, it's faster to graph it out. If you graph h(n) and g(n) you'll see that g(n) surpases h(n) at approximately n = 74.

So armed with this, and a list of all n's for n < 74, you can prove that it is impossible. ;) And it saves a lot of work and explanation.

This is the kind of method I think TheSvin wanted to try with the "if PF = 1 eax = -1 else ax = -1" challenge. But I don't exactly know how to begin adapting mathematical theory to a 5 byte algorithm. <scratches head>

It's interesting though.

**iblis**, good explaination. That is what I thought in my head - I knew h(n) was logithmic and g(n) linear, and they cross each other at two points. I also knew I'd have to test some values, so I wrote the code. Once (n) is large enough I am done - it is not important to know what the cross over point is imho. My algo is overkill for n=74, but maybe I can use it again. :) I hear that is the difference between engineering and mathematics - in math they want to know the cross over point, in engineering it is okay just to be sure of the answer. For other problems it would be very important not to test more values than needed, but this is not such a case.

:)

I like it more and more.

I thank you both iblis and bitRake for getting involved into it.

Now look closely into condition of the problem:

It doesn't tell anything about numeric system.

The only thing is known that it is position numeric system and radix

of it is integer.

Now I'll give you a hint:

Instead of looking for n make radix of numeric system a subject

of your research and you'll find answer very fast.

I like it more and more.

I thank you both iblis and bitRake for getting involved into it.

Now look closely into condition of the problem:

It doesn't tell anything about numeric system.

The only thing is known that it is position numeric system and radix

of it is integer.

Now I'll give you a hint:

Instead of looking for n make radix of numeric system a subject

of your research and you'll find answer very fast.

Svin,

Let's assume the number is in decimal format Then (n+1)^2 can be decomposed as (a+10b+100c+1000d+....)^2 . Likewise (n-1)/2 can be decomposed as (a+10b+100c+1000d+....-2)/2, where a,b,c,d...are the decimal digits. Expanding the first expression gives (a^2+100B^2+10000c^2+1000000d^2+...+(lots of cross products)) . Expanding the second expression gives (a/2+5b+50c+500d+...-1) . Now it can be seen that every digit in the (n+1)^2 expression has a square term, while every digit in the (n-1)/2 expression only has a linear term. Therefore, the first expression will ALWLAYS be greater than the second expression and the second expression has no chance of being equal to the first expression. The same argument holds true for any radix you wish to use. Ratch

Let's assume the number is in decimal format Then (n+1)^2 can be decomposed as (a+10b+100c+1000d+....)^2 . Likewise (n-1)/2 can be decomposed as (a+10b+100c+1000d+....-2)/2, where a,b,c,d...are the decimal digits. Expanding the first expression gives (a^2+100B^2+10000c^2+1000000d^2+...+(lots of cross products)) . Expanding the second expression gives (a/2+5b+50c+500d+...-1) . Now it can be seen that every digit in the (n+1)^2 expression has a square term, while every digit in the (n-1)/2 expression only has a linear term. Therefore, the first expression will ALWLAYS be greater than the second expression and the second expression has no chance of being equal to the first expression. The same argument holds true for any radix you wish to use. Ratch

**Ratch**, how can that be true?

n=3

(n+1)^2 = 16

Sum of digits (base 2) = 1

(n-1)/2 = 1 :eek:

------------------------------------------

n=5

(n+1)^2 = 36

Sum of digits (base 2) = 2

(n-1)/2 = 2 :eek:

```
xor esi, esi ; (n+1)
```

_0:

mov eax, esi

mul esi ; (n+1)^2

; count bits in EDX:EAX (base 2)

; this is slow, but fun! :)

or ebx,-1

_1: bsf ecx,eax

btr eax,ecx

inc ebx

jc _1

or eax,-1

_2: bsf ecx,edx

btr edx,ecx

inc eax

jc _2

add eax, ebx

; compare to (n-1)/2; ECX = (n+1)

lea eax, [eax*2 + 2]

sub eax, esi

je _x

_3:

inc esi

jns _0

int3

_x:

invoke _OUTPUT_, esi

jmp _3

**Svin**, I thought a little about this when I wrote the base 10 code. This is fun - you are a good teacher. You turn like a worm - that is the reason I have explicitly stated the problem again in my own words. I am eager for your surprises! ;)

**pwnage.**:grin:

BITrake,

Yes, looks like I did not set up the conditions properly. This problem looks intractable for algebraic equations because the values change in discrete steps. It appears that brute force computing in the way to go for this problem. Sort of like Fermat's Last Thoerem. Ratch

Yes, looks like I did not set up the conditions properly. This problem looks intractable for algebraic equations because the values change in discrete steps. It appears that brute force computing in the way to go for this problem. Sort of like Fermat's Last Thoerem. Ratch

**Ratch**, I don't think it requires brute force for this problem - my ASM skills are better than my math. :) I will try to work through the math though - I need the practice. Good to see another person join in the discussion.

It was very easy task.

Origianl qeustion from my book was harder.

(sum of digits in (n+1)^2=n(n-1)/2)

Now method:

solve equation

(n-1)/2=1

then radix would be

(n+1) and (n+1)^2

since in (n+1) radix system the number would look like

100

and in (n+1)^2 radix system

the number would look like 10

as you can see in both systems sum of digits equal 1.

It was too easy.

To train yourself find number

(n+1)^2 that have sum of digits equal to n(n-1)/2

It's easy since you now know the way.

Origianl qeustion from my book was harder.

(sum of digits in (n+1)^2=n(n-1)/2)

Now method:

solve equation

(n-1)/2=1

then radix would be

(n+1) and (n+1)^2

since in (n+1) radix system the number would look like

100

and in (n+1)^2 radix system

the number would look like 10

as you can see in both systems sum of digits equal 1.

It was too easy.

To train yourself find number

(n+1)^2 that have sum of digits equal to n(n-1)/2

It's easy since you now know the way.

Sort of like Fermat's Last Thoerem

What do you mean by " Fermat's Last Thoerem"?

Might be "Fermat's Big Theorem"?

It was proved using analitic geometry (trough curves of 3rd d. - elipsoids)

and the proof has nothing to do with brute force in computers.

Svin,

You are right about FLT not needing a computer. I was thinking of the 4 color map problem proof which did rely on copious amounts of computer resources. See http://www.pbs.org/wgbh/nova/proof/ for what I mean by FLT. Ratch

You are right about FLT not needing a computer. I was thinking of the 4 color map problem proof which did rely on copious amounts of computer resources. See http://www.pbs.org/wgbh/nova/proof/ for what I mean by FLT. Ratch

I read the artical before.

But we in Russia call it Big Theorem or Major Theorem,

to differ it from Minor Theorem.

I don't know why it called Last in the West.

How do you call Minor Theorem?

As to interview, from practical point of view it's uselles.

To understand Wiles proof one should read first Utaka Taniyama. Then Wiles proof that is based on it. ~ 250 pages of reading.

And very few people can understand it.

But we in Russia call it Big Theorem or Major Theorem,

to differ it from Minor Theorem.

I don't know why it called Last in the West.

How do you call Minor Theorem?

As to interview, from practical point of view it's uselles.

To understand Wiles proof one should read first Utaka Taniyama. Then Wiles proof that is based on it. ~ 250 pages of reading.

And very few people can understand it.

Svin,

Well, the rest of the world calls it FLT, because it was his last theorem. I don't know what the rest of the world calls the Minor Thoerem. If fact, I don't know what the Minor Theorem is, because I am not a mathematician, or familiar with Fermat's work on number theory. Ratch

Well, the rest of the world calls it FLT, because it was his last theorem. I don't know what the rest of the world calls the Minor Thoerem. If fact, I don't know what the Minor Theorem is, because I am not a mathematician, or familiar with Fermat's work on number theory. Ratch

I have heard it called both. I don't think FLT is exclusively a western term, nor is FBT exclusively a non-western term.

IIRC the theorem says a^n + b^n = c^n is impossible to solve for non-zero integer values and n > 2.

I don't see what this has to do with '(n-1)/2 = sumdigits((n+1)^2)' though. :confused:

IIRC the theorem says a^n + b^n = c^n is impossible to solve for non-zero integer values and n > 2.

I don't see what this has to do with '(n-1)/2 = sumdigits((n+1)^2)' though. :confused: