Posts Tagged ‘math

19
May
09

[C++] Numbers with 6 divisors where none of the divisors are primes > 5

My uncle phoned me up to day with a question:

N is a number that has exactly 6 factors.
One of the factors is 1, and another is the number itself.
None of the prime factors of N can be greater than 5
Find a method for calculating a set of vales that would suit N.

Well. To be honest, after literally hours of trying to work out how to do this, I gave up and decided to program a brute force algorithm that would do this for me:

#include "stdafx.h"
#include "math.h"

int main()
{
	//Algorithm to calculate numbers where
	//Number of divisors < 7
	//None of the prime divisors > 5
	for(int i=1;i<100;i++) {
		int dc = 0; //divisor count
		bool pc = true; //prime check
		for(int k=1;k<(i/2)+1;k++) { //loop through all the numbers up to (n/2)+1
			if(i%k==0) { //check to see if divides with no remainder
				dc++; //increase divisor count
				if(dc > 5) { //if divisor count greater than 5, then quit - this number is not valid
					dc++;
					break;
				} else { //else we need to check the divisor
					if(k>5) {//if the divisor is bigger than 5, we need to check if it is prime
						bool ip = true; //is prime?
						for(int j = 2; j <= sqrt((double)k); j++)  //loop through the possible values
							if(k % j == 0) //check remainder
								ip=false;
						if(ip==true) { //sorry, its too big to be prime. quit
							pc=false;
							break;
						}
					}
				}
			}
		}
		if(dc==5 && pc==true) //check number is prime valid and has 6 divisors
			printf("Valid Number %d, \n", i);
	}
	return 0;
}

That would produce the list of valid numbers, those being:
12 : [1, 2, 3, 4, 6, 12]
18 : [1, 2, 3, 6, 9, 18]
20 : [1, 2, 4, 5, 10, 20]
32 : [1, 2, 4, 8, 16, 32]
45 : [1, 3, 5, 9, 15, 45]
50 : [1, 2, 5, 10, 25, 50]
75 : [1, 3, 5, 15, 25, 75]

Advertisements
20
Apr
09

[C++] Approximating Squares: Babylonian Method

const double EPSILON = 1.0e-16;

double BabylonianMethod(double value, int& counter)
{
	counter = 1;
	double guess=value/2;
	double result = ((value/guess)+guess)/2;
	while(abs(result-guess)>EPSILON)
	{
		guess = result;
		result = ((value/guess)+guess)/2;
		counter++;
	}
	return result;
}

Usage:

	int counter;
	double value = 10;
	double res = BabylonianMethod(value, counter);
	std::cout << std::setprecision(16);
	std::cout << "Square root of " << value << " is " << res << "\n";
	std::cout << "Number of iterations is " << counter << "\n";

Would Output:
Square root of 10 is 3.16228
Number of iterations is 6

19
Apr
09

[C++] Approximating Squares: Bakhshali Approximation

double BakhshaliApproximation(double value, int n)
{
	return (n+((value - n*n)/(2*n)))-(((value - n*n)/(2*n))*((value - n*n)/(2*n))/(2*(n+((value - n*n)/(2*n)))));
}

Usage:
Where Value = the square you wish to find and N = Closest perfect square to Value.

std::cout << BakhshaliApproximation(9.2345, 3) << "\n";

Would Output:
3.038832022859598

which is approx = Sqrt(9.2345)

04
Apr
09

[Javascript] Synthetic Division

An easier method of dividing polynomials.
This function uses synthetic division to divide a polynomial by a simple ax+b
The polynomial must be in the format of a1x^n + a2x^(n-1) + a3x^(n-2)…aix^(nn)

function syntheticDivision(poly, division) {
	//Format the equations correctly
	poly = poly.replace(/(--|\+\+)/g, "+");
	poly = poly.replace(/(-\+|\+-)/g, "-");
	poly = poly.replace(/^\+/g, "");
	poly = poly.replace(/\s/g, "");
	division = division.replace(/(--|\+\+)/g, "+");
	division = division.replace(/(-\+|\+-)/g, "-");
	division = division.replace(/^\+/g, "");
	division = division.replace(/\s/g, "");
	//Remove all x's and powers
	poly = poly.replace(/x\^?\d?/g, "");
	//Add spaces to the equation to break it apart
	poly = poly.replace(/([+-])/g, " $1");
	//Split the equation at the spaces
	var equ = poly.split(" ");
	//Rearrange division to equal 0
	var divide = division.split("x")[0]
	if(divide==""){ divide="1"; }
	division = (~Number(division.split("x")[1])+1)/divide;
	//Begin division
	var output = ""
	var lastTerm = "0"
	for(var i=0;i<equ.length-1;i++) {
		if(equ[i].split("x")=="+" || equ[i].split("x")=="-") { equ[i] = equ[i]+"1" }
		var dt = Number(Number(equ[i]) + Number(lastTerm));
		var x = (dt/divide);
		output += x + "x^" + (equ.length-i-2) + "+";
		lastTerm = dt * division;
	}
	//Format output
	output = output.replace(/\+([+-])/g, "$1");
	output = output.replace(/0x\^\d/g, "");
	output = output.replace(/(x\^0)?\+$/g, "");
	output = output.replace(/x\^1/g, "x");
	//Calculate remainder
	output += " : Remainder [" + String(Number(equ[equ.length-1]) + Number(lastTerm)) + "]";
	return(output);
}

Usage:

<script language="javascript" type="text/javascript">
var poly = "14x^4-5x^3-11x^2-11x+8";
var division = "2x-1";
alert(syntheticDivision(poly, division));
</script>

Would output:
7x^3 + 1x^2 – 5x -8 : Remainder [0]

04
Apr
09

[Javascript] Simple Polynomial Long Division

This function uses long division to divide a polynomial by a simple ax+b

The polynomial must be in the format of ax^n + bx^(n-1) + cx^(n-2)…zx^(nn)

The function itself relies upon 4 other functions in order to work, these are used to carry out basic operations on the terms in the polynomail:

//Used to break an { ax^n } into its compontents
function extractCompontents(Term, constantChar) {
	var Comps = new Array();
	Comps[0] = Term.split(constantChar)[0];
	Comps[1] = Term.split("^")[1];
	if(Comps[0] == "") { Comps[0]=1; }
	if(String(Comps[1]) == "undefined") { Comps[1]=1; }
	return Comps;
}
function divideTerm(Term1, Term2, constantChar) {
    var extTerm1 = extractCompontents(Term1, constantChar)
	var extTerm2 = extractCompontents(Term2, constantChar)
	return String(extTerm1[0]/extTerm2[0]) + constantChar + "^" + String(extTerm1[1]-extTerm2[1]);
}
function multiplyTerm(Term1, Term2, constantChar) {
	var extTerm1 = extractCompontents(Term1, constantChar)
	return String(extTerm1[0] * Term2) + constantChar + "^" + String(extTerm1[1]);
}
function subtractTerm(Term1, Term2, constantChar) {
    var extTerm1 = extractCompontents(Term1, constantChar)
	var extTerm2 = extractCompontents(Term2, constantChar)
	if(extTerm1[1] != extTerm2[1]) { return null; }
	return String(extTerm1[0]-extTerm2[0]) + constantChar + "^" + String(extTerm1[1]);
}

The function itself is as follows:

function longAlgebraicDivision(poly, division) {
	//Format the equations correctly
	poly = poly.replace(/(--|\+\+)/g, "+");
	poly = poly.replace(/(-\+|\+-)/g, "-");
	poly = poly.replace(/^\+/g, "");
	poly = poly.replace(/\s/g, "");
	division = division.replace(/(--|\+\+)/g, "+");
	division = division.replace(/(-\+|\+-)/g, "-");
	division = division.replace(/^\+/g, "");
	division = division.replace(/\s/g, "");
	//Add spaces to the equation to break it apart
	poly = poly.replace(/([+-])/g, " $1");
	//Split the equation at the spaces
	var equ = poly.split(" ");
	//Begin the division
	var output = ""
	var lastTerm = ""
	for(var i=0;i<equ.length-1;i++) {
		var term = equ[i];
		if(i==0) {
			var dt = divideTerm(term, division.split("x")[0], "x");
			output += dt + "+";
			dt = multiplyTerm(dt, division.split("x")[1], "x");
			lastTerm = dt;
		}else{
			var dt = subtractTerm(term, lastTerm, "x");
			dt = divideTerm(dt, division.split("x")[0], "x");
			output += dt + "+";
			dt = multiplyTerm(dt, division.split("x")[1], "x");
			lastTerm = dt;
		}
	}
	//Format output
	output = output.replace(/\+([+-])/g, "$1");
	output = output.replace(/x\^0\+$/g, "");
	output = output.replace(/x\^1/g, "x");
	//Calculate remainder
	lastTerm = lastTerm.replace(/x\^0/g, "");
	output += " : Remainder [" + String(Number(equ[equ.length-1]) - Number(lastTerm)) + "]";
	return output;

Usage:

<script language="javascript" type="text/javascript">
var poly = "14x^4-5x^3-11x^2-11x+8";
var division = "2x-1";
alert(longAlgebraicDivision(poly, division));
</script>

Would output:

7x^3 + 1x^2 – 5x -8 : Remainder [0]

04
Apr
09

[Javascript] Divide Simple Algebraic Terms

Been working on some maths things today, and wrote this function to divide basic terms.
Will work on any string in the format of:
ax^n; where a = any number, x = any constant character, n = any number

function divideTerm(Term1, Term2, constantChar) {
	//The coefficient of the first Term
	var Term1coeff = Term1.split(constantChar)[0];
	//The power of the first Term
	var Term1power = Term1.split("^")[1];
	//The coefficient of the second Term
	var Term2coeff = Term2.split(constantChar)[0];
	//The power of the second Term
	var Term2power = Term2.split("^")[1];
	//If no coefficient, set to 1
	if(Term1coeff==""){Term1coeff=1;}
	//If no power, set to 1
	if(String(Term1power)=="undefined"){Term1power=1;}
	//If no coefficient, set to 1
	if(Term2coeff==""){Term2coeff=1;}
	//If no power, set to 1
	if(String(Term2power)=="undefined"){Term2power=1;}
	//Divide the two coefficients, add the character and claret, subtract the two powers
	return String(Term1coeff/Term2coeff) + constantChar + "^" + String(Term1power-Term2power);
}

Usage:
Sample project:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Dividing Alg Terms</title>
<script language="javascript" type="text/javascript">
function divideTerm(Term1, Term2, constantChar) {
	var Term1coeff = Term1.split(constantChar)[0];
	var Term1power = Term1.split("^")[1];
	var Term2coeff = Term2.split(constantChar)[0];
	var Term2power = Term2.split("^")[1];
	if(Term1coeff==""){Term1coeff=1;}
	if(String(Term1power)=="undefined"){Term1power=1;}
	if(Term2coeff==""){Term2coeff=1;}
	if(String(Term2power)=="undefined"){Term2power=1;}
	return String(Term1coeff/Term2coeff) + constantChar + "^" + String(Term1power-Term2power);
}

function divide() {
	document.getElementById("result").value = divideTerm(
		document.getElementById("trm1").value,
		document.getElementById("trm2").value,
		document.getElementById("char").value);
}
</script>
</head>

<body>
<form id="form1" name="form1" method="post" action="">
  <table width="297" border="0">
    <tr>
      <td width="143"><strong>Term 1: </strong></td>
      <td width="144"><input name="textfield3" type="text" id="trm1" value="147x^23" /></td>
    </tr>
    <tr>
      <td><strong>Term 2: </strong></td>
      <td><input name="textfield4" type="text" id="trm2" value="24.5x^19" /></td>
    </tr>
    <tr>
      <td><strong>Constant Character: </strong></td>
      <td><input name="textfield" type="text" id="char" value="x" /></td>
    </tr>
    <tr>
      <td colspan="2"><div align="center">
        <br />
	    <input name="button" type="button" value="Divide" onclick="divide()" />
      </div></td>
    </tr>
    <tr>
      <td>&nbsp;</td>
      <td>&nbsp;</td>
    </tr>
    <tr>
      <td><strong>Result:</strong></td>
      <td><input type="text" name="textfield2" readonly="true" id="result"/></td>
    </tr>
  </table>
  </form>
</body>
</html>

E.g.
147xy^23/24.5xy^19 = 6xy^4

27
Mar
09

[JavaScript] Determine if Number is Prime

Little script to determine if a number is prime or not.
Can be sped up by removing the document.write lines, which are only displayed to the user to show what tests are being run.

function isPrime(pTest) {
   if((pTest == 2) || (pTest==-2)) {
      document.write('Number [' + pTest + '] is prime' + "<br > n");
      return true;
   } else if(pTest%2 == 0) {
      document.write(pTest + "/" + 2 + " Remainder = " + pTest%2 + "<br > ");
      return false;
   } else if ((pTest==1) || (pTest==0) || (String(pTest).indexOf('.') != -1)) {
      document.write('Numbers [0; 1; decimals] are not prime' + "<br > n");
      return false;
   } else {
      for (i = 3; i * i <= pTest; i += 2) {
         if (pTest % i == 0) {
            document.write(pTest + ";/" + i + " Remainder = 0<br > ");
            return false;
         }else{
            document.write(pTest + "/" + i + " Remainder = " + pTest%i + "<br > ");
         }
      }
      return true;
   }
}

Usage:

var n = prompt("Enter a number to test for prime", 53);
alert(isPrime(n));

Would output:

53/3 Remainder = 2
53/5 Remainder = 3
53/7 Remainder = 4

[Alert]True