But i don old now, since dhtml18 all the way to dhtml118 - that is like 100 years difference.

DharkPoet:


Here you go @bolkay47 done in PHP

<?php
// Find the GCD between two numbers
function getGCD($num1, $num2) {
   while ($num2 != 0){
     $t = $num1 % $num2;
     $num1 = $num2;
     $num2 = $t;
   }
   return $num1;
}

function PHIfunction($n) {
	if ($n == 1) {
		return 1;
	}
	$count = 0;
	for ($i=1; $i < $n; $i++) {
		if (getGCD($i, $n) === 1) {
			$count++;
		}
	}
	return $count;
}

echo PHIfunction(9);
// returns 6

echo PHIfunction(20);
// returns 8

echo PHIfunction(87109)
// returns 79180

?>

Nice one Sir!.....but where is the OP of this thread?
This is the answer in C#.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  private static List<int> primes = GenerateRangeOfPrimes(1000,5000);

  static void Main()
  {
      //Problem 70
      DateTime start = DateTime.Now;
      decimal min = 100;
      int number = 1;

      for (int j = primes.Count - 1; j >= 0; j--)
          for (int k = j - 1; k >= 1; k--)
          {
              int i = primes[j]*primes[k];
              if (i < 10000000)
              {
                  int totient = (primes[j] - 1)*(primes[k] - 1);
                  if (IsPermutation(i, totient))
                      if ((decimal) i/totient < min)
                      {
                          min = (decimal) i/totient;
                          number = i;
                          Console.WriteLine(number + ": " + min + " p1: " + primes[k] + " p2: " + primes[j]);
                      }
              }
          }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }

  private static bool IsPermutation(int m,int n)
  {
      char[] c = m.ToString().ToCharArray();
      char[] d = n.ToString().ToCharArray();
      Array.Sort(c);
      Array.Sort(d);
      string s = new string(c);
      string t = new string(d);
      if (s == t) return true;
      return false;
  }

  private static bool IsPrime(int n)
  {
      if (n < 2) return false;
      if (n == 2) return true;
      for (long i = 2; i <= Math.Sqrt(n); i++)
          if (n % i == 0) return false;
      return true;
  }

  private static List<int> GenerateRangeOfPrimes(int m,int n)
  {
      var p = new List<int> { 2, 3 };
      for (int i = 5; i <= n; i += 2)
          if (IsPrime(i))
              p.Add(i);
      while (p[0] < m)
          p.Remove(p[0]);
      return p;
  }
}
}

The permutation which produces the smallest ratio is 8319823 and this produces the fraction 1.0007090511248112805403174047.
Credits: Sir Alan of http://siralansdailyramble..com.ng

^^^great work, we are seeing great programmers on this thread

bolkay47:
Nice one Sir!.....but where is the OP of this thread?
This is the answer in C#.

...
  private static bool IsPrime(int n)
  {
      if (n < 2) return false;
      if (n == 2) return true;
   

for (long i = 2; i <= Math.Sqrt(n); i++)

if (n % i == 0) return false;
      return true;
  }

  
}
}

The permutation which produces the smallest ratio is 8319823 and this produces the fraction 1.0007090511248112805403174047.
Credits: Sir Alan of http://siralansdailyramble..com.ng

Should have computed the prime number outside the loop that way the program will run faster.
Computing 'isPrime(n)' every time the loop runs,when n is static, is just disastrous to performance.

asalimpo:


Should have computed the prime number outside the loop that way the program will run faster.
Computing 'isPrime(n)' every time the loop runs,when n is static, is just disastrous to performance.

Good evening.
You may be right. The solution gets the job done and it took '00:00:00.1405923' which in my opinion is still good....
if you have any other method, you can put it forward.I will be glad to see it.
Can you help me locate the OP?

dhtml118:
But i don old now, since dhtml18 all the way to dhtml118 - that is like 100 years difference.

I checked your website few minutes ago, it's really nice. yeah, my first time.
I envy professional web developers. Nice one!
Bearnana, do you have a website?

bolkay47:
Good evening.
You may be right. The solution gets the job done and it took '00:00:00.1405923' which in my opinion is still good....
if you have any other method, you can put it forward.I will be glad to see it.
Can you help me locate the OP?

It's not a matter of 'may be right'. I am right.
calling a function once,When the function doesnt even need to b called more than once, vs calling it n times, is atrocious?
It has nothing to do with pc clock timing.
It's outrageously bad and shouldnt be overlooked.
what if n is 1 000 000 or 1 000 000 000 000 000 000 000
and the code is used in a commercial/or critical capacity?

Even if the code isnt critical it is code coding practice to optimize your code for efficiency.

i dont have a solution. I was all about highlighting that glaring blasphemy!

I can see that we have all been busy...

Has programming section come back to life?

It can come back to life, if we want it back to life. This is the first really interesting topic in a long while.

I move the motion that we bring this board to life - what do you say guys?

bolkay47:
Good evening.
You may be right. The solution gets the job done and it took '00:00:00.1405923' which in my opinion is still good....
if you have any other method, you can put it forward.I will be glad to see it.
Can you help me locate the OP?

Using GPS abi wetin.....

dhtml118:
It can come back to life, if we want it back to life. This is the first really interesting topic in a long while.

I move the motion that we bring this board to life - what do you say guys?

Una too like fight....

seunthomas:
Using GPS abi wetin.....

Lol, just joking sir. Have fun!

when people and threads like this keeps steady, our programming section becomes lively,

but this one seun and his mods are busy banning people that that makes the place lively..

anyway guys keep it coming, we beginers are enjoying and learnign a lot from things like this.

Na who them ban again o? Is that why there are no more people to post ni? I thought I was the one person getting banned repeatedly?

It's an object oriented test, guess you didn't read the instructions...

bearnana:
With PHP

<?php

function get_good_eggs( $all_eggs, $bad_eggs) {

$bad_eggs = array_intersect($all_eggs,$bad_eggs);
$good_eggs = array_diff($all_eggs,$bad_eggs);
foreach($bad_eggs as $key => $value) {
$good_eggs[] = $value;
}
return $good_eggs;
}

?>

Apologies for my shrewd variable names

Anybody available for a healthy problem solving session in Go/Scala later in the day, say around 4/5pm after work?

But before then, I have a simple question.. I don't need to see code; just logical reasoning..
(Taken from an interview of a company I worked for)

In a co-ordinate plane, a line segment is drawn from the origin to a point A(x,y). With great efficiency, find the number of cells the line passes through Assuming X and Y are ints...

Google may not be of too much help, this is largely theoretical.

Mod: let's have more of this kind of questions as the ones involving code can easily be Googled or outsourced.. This tests the fundamental knowledge of computer science.. Programming is more of thinking than coding

DanielTheGeek:
But before then, I have a simple question.. I don't need to see code; just logical reasoning..
(Taken from an interview of a company I worked for)

In a co-ordinate plane, a line segment is drawn from the origin to a point A(x,y). With great efficiency, find the number of cells the line passes through Assuming X and Y are ints...

Google may not be of too much help, this is largely theoretical.

Mod: let's have more of this kind of questions as the ones involving code can easily be Googled or outsourced.. This limits the participation of programmers with less fundamental knowledge of computer science.. Programming is more of thinking than coding

Assuming the length of cells are 1, same with Y and X.

Then determining the line in which the cells passes through would be;
1) Incorporating the straight line formula y = mx + b.
2) go or loop through each value Y(with interval of size 1) and compare also with all X values.
3) And then just scale the X and Y values to it's nearest whole number and there you have the answer.

Illustrating step 2 and 3:
For example at point 1 to 2 for Y;
X values will be 0.1, 0.2,...,0.9, 1, 1.1, ...., 2,2.1,- 2.5. using the equation at every point in the Y value range.
Scaling x:
Just use a function to round up decimal values to it nearest whole number, filter repeating numbers and store result in a variable.
The result will be (1,0),(1,1),(1,2) ==>(y,x) format.

And those are the cells when y is 1.
Then continue for the rest and you have your solution.

Nice try man, I'm really impressed and glad you gave this a shot... However you have not given a correct answer or approach...
Let v be = gcd of X and Y


Why:
Remember that I'm not looking for an actual solution, think of a logic that when applied the solution could be worked even into a program..

4kings:

Assuming the length of cells are 1, same with Y and X.

Then determining the line in which the cells passes through would be;
1) Incorporating the straight line formula y = mx + b.
2) go or loop through each value Y(with interval of size 1) and compare also with all X values.
3) And then just scale the X and Y values to it's nearest whole number and there you have the answer.

Illustrating step 2 and 3:
For example at point 1 to 2 for Y;
X values will be 0.1, 0.2,...,0.9, 1, 1.1, ...., 2,2.1,- 2.5. using the equation at every point in the Y value range.
Scaling x:
Just use a function to round up decimal values to it nearest whole number, filter repeating numbers and store result in a variable.
The result will be (1,0),(1,1),(1,2) ==>(y,x) format.

And those are the cells when y is 1.
Then continue for the rest and you have your solution.

DanielTheGeek:
Nice try man, I'm really impressed and glad you gave this a shot... However you have not given a correct answer or approach...
Let v be = gcd of X and Y

What's v and why do i need greatest common divisor here?
Hint?
Moreso, why is the approach not correct?

DanielTheGeek:
But before then, I have a simple question.. I don't need to see code; just logical reasoning..
(Taken from an interview of a company I worked for)

In a co-ordinate plane, a line segment is drawn from the origin to a point A(x,y). With great efficiency, find the number of cells the line passes through Assuming X and Y are ints...

Google may not be of too much help, this is largely theoretical.

Mod: let's have more of this kind of questions as the ones involving code can easily be Googled or outsourced.. This tests the fundamental knowledge of computer science.. Programming is more of thinking than coding

my deduction

if n is the number of cells

1. if x = y, then n = x = y
2. if x is odd or y is odd n = (x + y) - 1
3. if they are both even n = (x + y) - (level of reduction * 2)
where level of reduction = the number of times we can divide by 2 until one of them is odd

is this right?

4kings:

What's v and why do i need greatest common divisor here?
Hint?
Moreso, why is the approach not correct?

v is a hint of the approach using gcd given that the line segment repeats v times.

And again you were asked to find the total number of cells the line passes through from one point to another.. Or rather come up with your own formula to derive an answer and you have to test this formula to give the most accurate (or near accurate) results possible.

I forgot to add: the diagram in the original question has a little caption:
From the figure below, the line segment from the origin to the point A(10,4) passes through 12 cells.

DanielTheGeek:


v is a hint of the approach using gcd given that the line segment repeats v times.

And again you were asked to find the total number of cells the line passes through from one point to another.. Or rather come up with your own formula to derive an answer and you have to test this formula to give the most accurate (or near accurate) results possible.

I forgot to add: the diagram in the original question has a little caption:
From the figure below, the line segment from the origin to the point A(10,4) passes through 12 cells.

Assuming my approach is correct, the total number of cells is determined by the total number of result coordinates.
Guess i would have to test my approach to determine if it's fit or not, but i don't see anything wrong with it.

Concerning formula, i can't think of one for now, but what i gave was an algorithm to follow.

orimion:

my deduction

if n is the number of cells

1. if x = y, then n = x = y
2. if x is odd or y is odd n = (x + y) - 1
3. if they are both even n = (x + y) - (level of reduction * 2)
where level of reduction = the number of times we can divide by 2 until one of them is odd

is this right?

x and y in the diagram are not equal.

But assuming x is 5 and y is 5.
n = (x+y)-1 = 9 is wrong.

If you trace the diagram to y and x at 5 max.
The number of cells are 6 not 9.

orimion:

my deduction

if n is the number of cells

1. if x = y, then n = x = y
2. if x is odd or y is odd n = (x + y) - 1
3. if they are both even n = (x + y) - (level of reduction * 2)
where level of reduction = the number of times we can divide by 2 until one of them is odd

is this right?

you didnt answer this

from your discussion about gcd, I googled it and found out rule 2 and 3 (both wrong) can be combined into

n = (x + y) - gcd

orimion:

my deduction

if n is the number of cells

1. if x = y, then n = x = y
2. if x is odd or y is odd n = (x + y) - 1
3. if they are both even n = (x + y) - (level of reduction * 2)
where level of reduction = the number of times we can divide by 2 until one of them is odd

is this right?

Really nice shot, but this is not correct....it's not also efficient, it seems you didn't get the question correctly... We are trying to calculate or come up with a formula that calculates the amount of cells a line passes through from the origin to it's destination.. In the figure I shared you can denote that based on the line the cells are moving either to the right or upwards, for x,y being positive integers (not equal)...the cells will move either to the left or downwards given that x,y are negative integers (not equal).. We aren't looking for the slope here but the amount of cells the line passed through..

4kings:

x and y in the diagram are not equal.

But assuming x is 5 and y is 5.
n = (x+y)-1 = 9 is wrong.

If you trace the diagram to y and x at 5 max.
The number of cells are 6 not 9.

check my rule 1 above

also 5 and 5 gives n = 5

DanielTheGeek:


Really nice shot, but this is not correct....it's not also efficient, it seems you didn't get the question correctly... We are trying to calculate or come up with a formula that calculates the amount of cells a line passes through from the origin to it's destination.. In the figure I shared you can denote that based on the line the cells are moving either to the right or upwards, for x,y being positive integers (not equal)...the cells will move either to the left or downwards given that x,y are negative integers (not equal).. We aren't looking for the slope here but the amount of cells the line passed through..

I changed my answer

if x = y, n = x = y
else n = (x+y) - gcd (or hcf)

4kings:

Assuming my approach is correct, the total number of cells is determined by the total number of result coordinates.
Guess i would have to test my approach to determine if it's fit or not, but i don't see anything wrong with it.

Concerning formula, i can't think of one for now, but what i gave was an algorithm to follow.

Yes...you did well, I was guessing you're into algorithm design thus the inspiration for the solution you tendered.. Please test, I may also be wrong (don't expect me to be right always) as I just scan through with my eyes and think of every logical reason why it wouldn't work. If it's not going to be the most efficient solution I will also consider it wrong as it'd be a wrong practice although yielding a possibly right answer..

Trust me I love being disproven... I really do, and I'm really enjoying this as I'm seeing things candidates never tried out..

DanielTheGeek:


Yes...you did well, I was guessing you're into algorithm design thus the inspiration for the solution you tendered.. Please test, I may also be wrong (don't expect me to be right always) as I just scan through with my eyes and think of every logical reason why it wouldn't work. If it's not going to be the most efficient solution I will also consider it wrong as it'd be a wrong practice although yielding a possibly right answer..

Trust me I love being disproven... I really do, and I'm really enjoying this as I'm seeing things candidates never tried out..

OKey-dokey.
I don't feel like opening python now, but will do later today.

orimion:


you didnt answer this

from your discussion about gcd, I googled it and found out rule 2 and 3 (both wrong) can be combined into

n = (x + y) - gcd

Minus GCD of what and what? I appreciate your effort but please don't just google and implement straight away..

Although I really commend your effort and at this stage you have gotten to I'd really like to know you more.... (That's for another day though, let's not derail) because you're getting a tad bit close to the actual efficient solution..but your answer is just not correct as it lacks mathematical logic..