/*
* The following iterative sequence is defined for the
* set of positive integers:
*
* n -> n/2 (n is even)
* n -> 3n + 1 (n is odd)
*
* Using the rule above and starting with 13,
* we generate the following sequence:
*
* 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
*
* It can be seen that this sequence (starting at 13 and finishing at 1)
* contains 10 terms. Although it has not been proved yet (Collatz Problem),
* it is thought that all starting numbers finish at 1.
*
* Which starting number, under one million, produces the longest chain?
*
* NOTE: Once the chain starts the terms are allowed to go above one million.
*/
/**
*
* @author Umang Bhatt
* bhatt.umang7@gmail.com
*/
public class Problem_14
{
/**
* contains logic for next no depending on the number
* @param no is the number from which next no is to be calculated
* @return the next number based on odd even logic
*/
public static long getNextNo(long no)
{
long ans;
if (no % 2 == 0)
{
ans = (no / 2);
}
else
{
ans = ((3 * no) + 1);
}
return ans;
}
/**
* gets no of items in chain for given no (chain ends at 1)
* @param no is the number for which the no of items in chain is to be found out
* @return no of items in chain
*/
public static int getChainItemCount(long no)
{
long ans = no;
int count = 1;
while (ans != 1)
{
ans = getNextNo(ans);
count++;
}
return count;
}
public static void main(String args[])
{
long maxCount = 0;
long maxNoProducesMaxCount = 0;
for (long i = 1; i <= 10_00_000; i++)
{
int ans = getChainItemCount(i);
if (ans > maxCount)
{
maxCount = ans;
maxNoProducesMaxCount = i;
}
}
System.out.print(" maxCount " + maxCount + "\nNO : " + maxNoProducesMaxCount);
}
}
Tuesday, June 26, 2012
Which starting number, under one million, produces the longest chain : Collatz Problem
first triangle number to have over five hundred divisors
/*
* The sequence of triangle numbers is generated by adding the natural numbers.
* So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first
* ten terms would be:
*
* 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
*
* Let us list the factors of the first seven triangle numbers:
*
* 1: 1 * 3: 1,3 * 6: 1,2,3,6 * 10: 1,2,5,10 * 15: 1,3,5,15 * 21: 1,3,7,21 * 28: 1,2,4,7,14,28
*
* We can see that 28 is the first triangle number to have over five divisors.
*
* What is the value of the first triangle number to have over five hundred
* divisors?
*/
/**
* if we get prime factors as p^a * q^b * .... *r^k then the no of factors we
* get will be (a+1)*(b+1)*...(k+1)
*
*
* eg prime factors of 441 are 3,3,7,7 that is 441 = 3^2 * 7^2 so the no of
* factors will be (2+1)*(2+1)=3*3=9
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
/**
* @author Umang B Bhatt
* bhatt.umang7@gmail.com
*/
class FactorNode
{
int count; // power
int no; // the actual number
@Override
public int hashCode()
{
return no;
}
@Override
public boolean equals(Object obj)
{
if (obj == null)
{
return false;
}
if (getClass() != obj.getClass())
{
return false;
}
final FactorNode other = (FactorNode) obj;
if (this.no != other.no)
{
return false;
}
return true;
}
}
public class Problem_12
{
/**
*
* @param numbers is the number for which prime factors are to be searched
* @return will return a list of prime factors for the given number
*/
public static List<Integer> primeFactors(long numbers)
{
long n = numbers;
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= n / i; i++)
{
while (n % i == 0)
{
factors.add(i);
n /= i;
}
}
if (n > 1)
{
factors.add((int) n);
}
return factors;
}
/**
*
* @param number is the number for which divisors are to be calculated
* @return HashMap<Integer, FactorNode> containing number and thir power
*/
public static HashMap<Integer, FactorNode> getFactorsWithPower(long number)
{
// maintain how many time a prime fator is repeated
// that is to know the power
HashMap<Integer, FactorNode> factorsMap = new HashMap<>();
for (Integer primeFactor : primeFactors(number))
{
FactorNode node = factorsMap.get(primeFactor);
if (node == null)
{
FactorNode newNode = new FactorNode();
newNode.no = primeFactor;
newNode.count = 1;
factorsMap.put(primeFactor, newNode);
}
else
{
node.count++;
}
}
return factorsMap;
}
/**
*
* @param number is the number for which we want to find number of factors
* @return no of factors of given number
*/
public static int getDivisorCount(long number)
{
int factorCount = 1;
HashMap<Integer, FactorNode> factorsMap = getFactorsWithPower(number);
// calculate no of factors
for (Integer key : factorsMap.keySet())
{
factorCount *= (factorsMap.get(key).count + 1);
}
return factorCount;
}
public static void main(String args[])
{
int i = 1;
int sum = 0;
primeFactors(441);
do
{
sum += i;
i++;
} while (getDivisorCount(sum) < 500);
System.out.println("Ans is : " + sum);
}
}greatest multiplication of 4 adjacent numbers in 20x20 grid
/*
* 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
* 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
* 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
* 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
* 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
* 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
* 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
* 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
* 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
* 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
* 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
* 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
* 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
* 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
* 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
* 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
* 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
* 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
* 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
* 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
*
*
* What is the greatest product of four adjacent numbers in any direction
* (up, down, left, right, or diagonally) in the 2020 grid?
*/
import java.util.StringTokenizer;
/**
*
* @author umang
* bhatt.umang7@gmail.com
*/
public class Problem_11
{
public static final String gridDataString = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"
+ "\n49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"
+ "\n81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"
+ "\n52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"
+ "\n22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"
+ "\n24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"
+ "\n32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"
+ "\n67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"
+ "\n24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"
+ "\n21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"
+ "\n78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"
+ "\n16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"
+ "\n86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"
+ "\n19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"
+ "\n04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"
+ "\n88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"
+ "\n04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"
+ "\n20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"
+ "\n20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"
+ "\n01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
//actual grid on which calculations are to be performed
static int grid[][] = new int[22][20];
// will be executed when class is loaded in memory
// will initialize the grid[] variable
static
{
// tokenize by new line char
StringTokenizer newLineTokenizer = new StringTokenizer(gridDataString, "\n");
int row = 0;
while (newLineTokenizer.hasMoreTokens())
{
int col = 0;
//tokenize by space character
StringTokenizer spaceTokenizer = new StringTokenizer(newLineTokenizer.nextToken(), " ");
while (spaceTokenizer.hasMoreTokens())
{
grid[row][col] = Integer.parseInt(spaceTokenizer.nextToken());
col++;
}
row++;
}
}
public static int getMultiplication(int row1, int col1, int row2, int col2, int row3, int col3, int row4, int col4)
{
int multiplication = 0;
try
{
multiplication = grid[row1][col1] * grid[row2][col2] * grid[row3][col3] * grid[row4][col4];
}
catch (ArrayIndexOutOfBoundsException aie)
{
// do nothing
}
return multiplication;
}
public static long performMultiplicationAndGetMax(int row, int col)
{
long max = 0;
//right
long result = getMultiplication(row, col, row, col + 1, row, col + 2, row, col + 3);
if (result > max)
{
max = result;
}
//left
result = getMultiplication(row, col, row, col - 1, row, col - 2, row, col - 3);
if (result > max)
{
max = result;
}
//down
result = getMultiplication(row, col, row + 1, col, row + 2, col, row + 3, col);
if (result > max)
{
max = result;
}
//up
result = getMultiplication(row, col, row - 1, col, row - 2, col, row - 3, col);
if (result > max)
{
max = result;
}
// diagonally
result = getMultiplication(row, col, row + 1, col + 1, row + 2, col + 2, row + 3, col + 3);
if (result > max)
{
max = result;
}
result = getMultiplication(row, col, row - 1, col - 1, row - 2, col - 2, row - 3, col - 3);
if (result > max)
{
max = result;
}
result = getMultiplication(row, col, row - 1, col + 1, row - 2, col + 2, row - 3, col + 3);
if (result > max)
{
max = result;
}
result = getMultiplication(row, col, row + 1, col - 1, row + 2, col - 2, row + 3, col - 3);
if (result > max)
{
max = result;
}
return max;
}
public static void main(String args[])
{
long max = 0;
for (int row = 0; row < grid.length; row++)
{
for (int col = 0; col < grid[row].length; col++)
{
long result = performMultiplicationAndGetMax(row, col);
if (result > max)
{
max = result;
}
}
}
System.out.println("Max is : " + max);
}
}
total of all the name scores in the file
/**
* Using names.txt (right click and 'Save Link/Target As...'), a 46K text file
* containing over five-thousand first names, begin by sorting it into
* alphabetical order. Then working out the alphabetical value for each name,
* multiply this value by its alphabetical position in the list to obtain a name
* score.
*
* For example, when the list is sorted into alphabetical order, COLIN, which is
* worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN
* would obtain a score of 938 53 = 49714.
*
* What is the total of all the name scores in the file?
*/
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.math.BigInteger;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
/**
*
* @author Umang B Bhatt bhatt.umang7@gmail.com
*/
public class Problem_22
{
/**
* name of file in which names are stored
*/
public static final String fileName = "names.txt";
/**
*
* @return the content of file as string
* @throws FileNotFoundException
*/
public static String getFileContent() throws FileNotFoundException
{
String data = "";
FileInputStream fis = new FileInputStream(fileName);
Scanner scanner = new Scanner(fis);
while (scanner.hasNextLine())
{
data += scanner.nextLine();
}
return data;
}
/**
*
* @param fileContent is the content of file
* @return returns a linked list of string containing names that were
* extracted from file content.
*/
public static LinkedList<String> getNamesFromFileData(String fileContent)
{
LinkedList<String> nameList = new LinkedList<>();
StringTokenizer strTOK = new StringTokenizer(fileContent, "\",");
while (strTOK.hasMoreTokens())
{
nameList.add(strTOK.nextToken());
}
return nameList;
}
/**
*
* @param name is the string for which sum is to be calculated
* @return sum of values of string.
*/
public static int getSumOfCharsInString(String name)
{
int sum = 0;
for (int i = 0; i < name.length(); i++)
{
sum += getIntValueForChar(name.charAt(i));
}
return sum;
}
/**
*
* @param c is the char for which value is to be calculated
* @return the value for char. eg. 1 for A, 2 for B and so on.
*/
public static int getIntValueForChar(char c)
{
int value = (int) c;
value -= 64; // 65 for A and so on
return value;
}
public static void main(String args[]) throws FileNotFoundException
{
//get the names in name list
String content = getFileContent();
LinkedList<String> nameList = getNamesFromFileData(content);
// sorth the list
Collections.sort(nameList);
BigInteger score = new BigInteger("0");
// sum up the score
for (int i = 0; i < nameList.size(); i++)
{
Integer j = (i + 1) * getSumOfCharsInString(nameList.get(i));
score = score.add(new BigInteger(j.toString()));
}
System.out.println("score is : " + score);
}
}
Subscribe to:
Posts (Atom)