phillip1882

here's another one of my favorites, in a similar vien.

there are two closed boxes. the host informs you that one box has 3 times the amount of money of the other.

you may open one box, and then based on the amount you see, switch if you so choose.

would it always be in your benefit to switch?

two rich men who have no idea how much money they currently have in their wallets meet. rich man A says to rich man B: "i'll bet you that i have more money in my wallet than you have in yours. In fact, let's switch wallets." should rich man B accept the wager?

i went to www.ideone.com and ran the following in both c and c++

#include <stdio.h>
int main(){
  int x = 7;
  int y = 3;
  int z = x^y;
  printf("%d \n",z);
  z = y^x;
  printf("%d \n",z);
  return 0;
}

and got

4

4

here's my coding challenge to you. xor 5 variables together on the same line with the ^ symbol, no side function.

but your code is doing exactly the same thing mine is, only more abstractly!

i was well aware in c that a^b = xor(a, b)

any way....

interesting solution for problem #1.

here's the way i was thinking of solving it.

#include <stdio.h>
int increment(int val){
  static int x = 0;
  x += 1;
  return x;
}
int main ( )
{
     int X = 0;

     if ( increment(X) != increment(X))
     {
           printf ( "impossible can happen" );
     }

     return 0;
}

which should in theory print the statement.

the second one was fairly simple; still not sure about the first. i have a couple ideas bouncing around though.

swap( int a, int b){

a = a^b

b = a^b

a = a^b

}

here's my next challenge.

find the smallest composite n, for which the base value 2 gives a false positive of the robin miller test.

the robin miller prime test is as follows.

take a odd number, n. subtract 1, and divide by 2 until odd, call this number d. call the number of divisions S.

if:

b^d != -1 or 1 mod n

or

if:

b^(2^r *d) != -1 mod n for 0 < r <= s

then n is composite.

else n is probably prime.

in other words find the first composite probably prime base 2.

i was thinking of posting a programming challange a month, both to help people sharpen their skills and to get some conversation going.

would there be interest in this?

if so; here's my first programming challenge.

most computer people know how to convert numbers to binary, but ternary computers are also possible.

my task for you is to write a program that can convert a decimal number to a ternary (base 3), and then be able to preform basic operations with two such numbers; addition, subtraction, multiplication, and division.

for extra points, also convert a decimal to balanced ternary, and have similar operations with them.

while pi is indeed transcendental, there are some nice representations of it none the less.

one of my personal favorites....

3 + 1/(7 +1/(15 +1/(31 +1/63....

edit: this is wrong I'm afraid.

a much more correct version is...

4/(1 +1/(3 +4/(5 +9/(7 +16/(9 +25/...

I am trying to conceptualize the notion of polynomial time. Can someone please tell me, in not-so-formal terms, what it means for something to be bounded by a polynomial?

 

Any help will be much appreciated.

a polynomial is an equation of the form n^a +n^(a-1) +n^(a-2)... n^3 +n^2 +n +1 where n is the size of the input.

to say a problem is bounded by a polynomial, generally means it's an "easy" problem.

the most common example i can think of would be sorting.

say you have a list of values of unknown magnitude (they can be as big or as small as desired) and you want to place them from smallest (closest to -infinity) to largest (closest to +infinity) there are many approaches to solving this problem, at worst it takes n^2 time, where n is the number of values, and at best it takes n*log(n). both are considered polynomial times.

to say a problem is non-polynomial, generally means it's a "hard" problem.

the classic non-polynomial time algorithm is the traveling salesman problem.

imagine you have a bunch of cities each with one or more connecting roads. is it possible to visit every city only once, without going back over the same road?

this sounds easy to solve, but is actually quite hard. with enough cities and enough roads, it could literally be "impossible" (take a very long time to determine).

the good news is, with most problems that are non-polynomial, once you have an answer, generally its fairly "easy" (polynomial time) to check if you're right.