What is arithmetic Expression that print this Sequence?

Question

1.00/5 (1 vote)

See more:

What is arithmetic Expression that print this Sequence?

8,7,8,7,8,7,.......

C++

x=??;
While(true){
x=[??????];            //Arithmetic Expression.
System.Out.Print(x+",");

}

Posted 24-May-12 8:16am

eng.Fadialia

Updated 24-May-12 8:35am

Wendelius

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 24-May-12 14:36pm

First of all, there is more than one. Did you try yourself? What's the problem?
--SA

Sergey Alexandrovich Kryukov 28-May-12 19:53pm

Now you can clearly see what I mean by "more than one"... :-)
--SA

3 solutions

Solution 3

If you asked for a bit operations expression (&, |, ~) instead of an arithmetic expression (+, -, *, /, %), the particular values have a simple solution:

x = ~x & 0x0F;

Reason: the bit pattern of 7 is 00000111 and of 8 is 00001000 --> 7 and 8 are the inverse bits of each other in the lowest 4 bits.
~00000111 & 00001111 = 00001000
~00001000 & 00001111 = 00000111

Cheers
Andi

Posted 28-May-12 1:25am

Andreas Gieriet

Updated 28-May-12 13:07pm

v2

Comments

Sergey Alexandrovich Kryukov 28-May-12 19:06pm

Yes, yes, yes. Another 5.
--SA

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Andreas Gieriet · Accepted Answer · 2012-05-24T08:59:00

Solution 2

Try something like

? = x₀
8 = x₁ = c - x₀ → x₀ = c - 8
7 = x₂ = c - x₁ → x₁ = c - 7 = 8 → c = ? → x₀ = ?
...
... = x_n+1 = c - x_n

So, what is c and what is x₀?
Too much said?

Have fun!
Cheers
Andi

Posted 24-May-12 8:59am

Andreas Gieriet

Comments

Sergey Alexandrovich Kryukov 24-May-12 15:09pm

It supposed to be just one expression. The rules of such games are: don't use index (you don't have it actually, this is a while loop), don't create additional variables. What's the problem? I gave a final answer, please see.
--SA

Andreas Gieriet 24-May-12 16:25pm

Read it carefully: I show a way to solve it with a hypothesis (assume the expression being of the form c - x) and mathematical induction to get the needed set of expressions to solve the initial constant and the constant in the hypothesis.

No additional variables...

Mapping that into the a programming language is peanuts.

c = 15, x_0 = 7
x = 7; ... x = 15 - x; ...

You can do further hypothesis, e.g. x_0 = k, x_(n+1) = a(x_n)^2 + b(x_n) + c

...(after some induction and equation solving)...:
k = 7
a = -1
b = 14
c = -41

x = 7; ... x = 14*x - x*x - 41;...

Or re-arranged:

x = 7; ... x = 8-(x-7)*(x-7); ...

So, you see, not new variables, just some hypothesis ans solving of the coefficients.

Cheers
Andi

Andreas Gieriet 24-May-12 16:32pm

BTW: I wrote my answer while you wrote yours. What's the problem? There is no "final" answer... ;-)

Sergey Alexandrovich Kryukov 24-May-12 17:47pm

Just a figure of speech... of course, it's not a problem. Yes, I realized that you put your solution at the same time; sorry for a confusing comment.
So, what is your one single expression. It should be just assignment x = f(x)... is it x = 8-(x-7)*(x-7)?
....

OK, got it. My 5.
--SA

Andreas Gieriet 25-May-12 4:33am

Thanks for your 5!
This playing around with the polynom solution is not realy meant to be used in real life, of course: why using complicated solutions when there are simple ones. I just like to tweak a bit with math as you may have noticed... ;-)

x = 15 - x; and your solution x = (x%2) + 7; are similarily simple - in real life I would take one or the other, but for sure not a more compilcated one.

As of playing with maths: see also my other comments on more generic solutions.

Cheers
Andi

Aescleal 24-May-12 17:28pm

+5 - I like this one, just subtraction - I doubt anyone can come up with a better answer. The power of maths, worship it!

Admittedly I wouldn't have got it without the explanation. Knuth factor 5/10.

Sergey Alexandrovich Kryukov 24-May-12 17:53pm

No, it's three subtractions and one multiplication. Excuse me, what does it mean: "Knuth factor 5/10"? I don't think I'm familiar with this notion. Could you please explain?
--SA

Aescleal 24-May-12 21:32pm

Isn't it just one subtraction... Every time around the loop it's:

x = 15 - x;

The Knuth comment was just that I reckoned this was the sort of maths you'd need to solve about half the exercises in "The Art of Computer Programming."

Sergey Alexandrovich Kryukov 24-May-12 21:44pm

:-), thank you...
Now, the expression in question is just this: x = 8-(x-7)*(x-7). This is correct.
--SA

Andreas Gieriet 25-May-12 3:38am

A simple general solution for sequences a,b,a,b,a,b,...
1) init: x = b;
2) loop: x = (a+b) - x;

E.g.
0,1,0,1,0,1,...: x = 1; x = 1 - x;
1,0,1,0,1,0,...: x = 0; x = 1 - x;
1,-1,1,-1,1,...: x = -1; x = -x;
17,25,17,25,...: x = 25; x = 42 - x;
etc.

Just for fun (if you like math), you can of course produce a whole variety of solutions for a,b,a,b,a,b,... of the form:

x = b; ...x = A*x*x + B*x + C...

where
A = can be chosen (parameter to produce the different solutions)
B = -A*(a+b)-1
C = A*a*b+(a+b)

E.g. A = -1, a = 8, b = 7:
x = 7; ...x = -(x*x) + 14*x - 41;... // x = (-1)*x*x + (-1)*(-1)*(7+8)-1 + (-1)*7*8 + (7+8)

Or with A = 1, a = 8, b = 7:
x = 7; ...x = x*x - 16*x + 71;...

Or with A = 1, a = -1, b = 1:

x = 1; ...x = x*x - x - 1;...

etc.

Have fun!
Cheers
Andi

Andreas Gieriet 25-May-12 2:14am

Thanks for your 5!
Yes, the simplest I came up with is x = 15 - x. I did show the "systematic" way, but it needs some first guess (the hypothesis).
Oscillating sequences (toggle between two values) are always of the form

x = c - x.

E.g. 0,1,0,1,...: x = 1; ... x = 1 - x; ...

The Rule for a,b,a,b,a,b... sequences:
1) init: x = b;
2) iteration: x = (a+b) - x;

Cheers
Andi

Sergey Alexandrovich Kryukov 25-May-12 11:45am

Well, there are many periodic functions, and one would need pretty much any of them, with modulo (%) being the simplest in the integer domain, hence the obvious starting point... call it hypothesis...
Thank you for this discussion.
--SA

Sergey Alexandrovich Kryukov · Accepted Answer · 2012-05-24T08:46:00

Solution 1

The solution of this problem requires a minute or so: x = 7; /* … */ x = (x % 2) + 7; that's it.

[EDIT]

One more solution: x = x + 2 * (x & 1) - 1; it can be the fastest on the CPUs where division operators are much slower than additive ones; and bit mask operators are always fast.

[EDIT]

More exactly, even faster solution, thanks to the great note by Andreas Gieriet, would be this: x = x + ((x & 1) << 1) - 1;

—SA

Posted 24-May-12 8:46am

Sergey Alexandrovich Kryukov

Updated 28-May-12 13:53pm

v5

Comments

Wendelius 24-May-12 15:10pm

Nice :)

Sergey Alexandrovich Kryukov 24-May-12 17:44pm

Thank you, Mika.
--SA

Andreas Gieriet 25-May-12 4:43am

My 5: simple and effective.
Andi

Sergey Alexandrovich Kryukov 25-May-12 11:43am

Thank you very much, Andreas.
--SA

Sergey Alexandrovich Kryukov 28-May-12 18:00pm

By the way: one more solution, probably the fastest -- want to take a look?
--SA

Andreas Gieriet 28-May-12 18:35pm

Yes. Maybe a bit-shift instead of multiply by 2 or adding it twice would further speed up,
e.g. x = x + ((x & 1) << 1) - 1
or x = x + (x & 1) + (x & 1) - 1.

Did you see my second solution 3: x = ~x & 0x0F;?

There is now a large selection for solving this homework... ;-)

Cheers
Andi

Sergey Alexandrovich Kryukov 28-May-12 19:04pm

Oh, sure! Thank you for this note. I'll credit this improvement in the answer.
--SA