Toroidal Array

This is an implementation and demonstration of a toroidal array class. The array nodes are each linked to 4 other nodes, allowing traversal of the cursor from one “edge” of the array to the other. Use the arrow buttons or click within the grid to move the cursor.

Language: JavaScript/jQuery
var toroidal_grid = null;
jQuery(document).ready(function() {
toroidal_grid = new Grid(5, 5, "grid");
});

function Grid(width, height, element_id) {
this.width = width;
this.height = height;
//default position is the center of the grid
//(or close to it if the grid dimensions are even numbers)
this.position = parseInt((width * height) / 2);

this.goToNode = function(node) {
//get the node's position from the end of its ID string
this.updateGrid((node.id).split("-").pop());
};

//helper functions for setting up node links
this.findWestBoundary = function(i) {
if ((i % this.width) == 0) {
return i + this.width - 1;
} else {
return i - 1;
}
};
this.findSouthBoundary = function(i) {
if (i >= ((this.width * this.height) - this.width)) {
return i % this.width;
} else {
return i + this.width;
}
};
this.findNorthBoundary = function(i) {
if (i < this.width) {
return (this.width * this.height - (this.width - i));
} else {
return i - this.width;
}
};
this.findEastBoundary = function(i) {
if ((i % this.width) == (this.width - 1)) {
return i - this.width + 1;
} else {
return i + 1;
}
};

this.nodes = [];
var west, south, north, east;
for (var i=0; i<width*height; i++) {
//populate the node array
this.nodes.push(
new GridNode(
this.findWestBoundary(i),
this.findSouthBoundary(i),
this.findNorthBoundary(i),
this.findEastBoundary(i)
)
);

//create the grid elements
var node = document.createElement("div");
if (i == this.position) {
node.className = "grid-node grid-node-active";
} else {
node.className = "grid-node grid-node-inactive";
}
node.id = "grid-node-" + i;
node.onclick = function() {toroidal_grid.goToNode(this);};

jQuery("#" + element_id).append(node);
}

this.updateGrid = function(newPos) {
//remove the active class from the previous node and make it inactive
var node = jQuery("#grid-node-" + this.position);
node.addClass("grid-node-inactive").removeClass("grid-node-active");

//store the new position
this.position = newPos;

//remove the inactive class from the new node and make it active
node = jQuery("#grid-node-" + this.position);
node.addClass("grid-node-active").removeClass("grid-node-inactive");
};

//handlers for arrow buttons
this.moveWest = function() {
this.updateGrid(this.nodes[this.position].west);
};
this.moveSouth = function() {
this.updateGrid(this.nodes[this.position].south);
};
this.moveNorth = function() {
this.updateGrid(this.nodes[this.position].north);
};
this.moveEast = function() {
this.updateGrid(this.nodes[this.position].east);
};
}

function GridNode(west, south, north, east) {
this.west = west;
this.south = south;
this.north = north;
this.east = east;
}
Project Euler Problem 14 – Longest Collatz sequence (Source)

The following iterative sequence is defined for the set of positive integers:

nn/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.

Language: Python 3
#!/usr/bin/python3
def getLength(n):
length = 1
while n != 1:
if n % 2 == 0:
n = int(n/2)
else:
n = 3 * n + 1
length += 1
return length

longestChain = 0
longestSeed = 0
limit = 1000000

for seed in range(1, limit, 1):
length = getLength(seed)
if length > longestChain:
longestChain = length
longestSeed = seed
print ('new longest chain: {} terms ({})'.format(longestChain, longestSeed))

print ('Longest chain: {} terms ({})'.format(longestChain, longestSeed))
Project Euler Problem 19 – Counting Sundays (Source)

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Language: Python 3
#!/usr/bin/python3
daysInMonth = {0:31, 1:28, 2:31, 3:30, 4:31, 5:30, 6:31, 7:31, 8:30, 9:31, 10:30, 11:31}
sundayCount = 0
seedYear = 1900
startYear = 1901
endYear = 2000
dayOfWeek = 0 # 0 meaning Monday, 6 meaning Sunday

for year in range(seedYear, endYear + 1):
for month in range(12):
# print ('First day of {}-th month in {} was index {}'.format(month, year, dayOfWeek))
if year >= startYear and dayOfWeek == 6:
sundayCount += 1
# update dayOfWeek to store the next month's first day of the week
if month == 1 and year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
dayOfWeek = (dayOfWeek + (daysInMonth[month] + 1)) % 7
else:
dayOfWeek = (dayOfWeek + (daysInMonth[month])) % 7

print ('There were {} first-of-the-month Sundays between {} and {}'.format(sundayCount, startYear, endYear))
Project Euler Problem 21 – Amicable numbers (Source)

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Language: Python 3
#!/usr/bin/python3
def getDivisorSum(n):
sum = 0
for x in range(1, int(n/2) + 1, 1):
if n % x == 0 and x != n:
sum += x
return sum

sums = []
amicable = []
limit = 10000
for n in range(limit):
sumN = getDivisorSum(n + 1)
if sumN > 0:
for x in sums:
if x[0] == sumN and x[1] == (n + 1) and x[0] != (n + 1):
amicable.append([(n + 1), x[0]])
sums.append([(n + 1), sumN])

amicableSum = 0
for pair in amicable:
print ('amicable pair: {}, {}'.format(pair[0], pair[1]))
amicableSum += pair[0] + pair[1]

print ('sum of {} pairs: {}'.format(len(amicable), amicableSum))
Project Euler Problem 35: Circular primes (Source)

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Language: Python 3
#!/usr/bin/python3
import math

def isPrime(n):
# trial by division
for i in range(3, int(math.pow(n, 0.5))+2, 2):
if n % i == 0:
return False
return True

def getRotations(prime):
# convert the number to a string and calculate the rotations by swapping characters.
# this could be optimized by not using strings
s = str(prime)
rotations = [prime]
for n in range(1, len(s)):
rotations.append(int(s[n:] + s[:n]))
# return a list of unique rotations only
# this avoids wasting time checking for primality on palindromes
return list(set(rotations))

def getCircularRotations(prime):
# returns a list containing circular prime(s), or an empty list

s = str(prime)
# primes which contain the digits 0, 2, 4, 5, 6, or 8 are not circular
# this is because at least one rotation of those numbers will not be prime
if any(i in s for i in '024568'):
return []
else:
rotations = getRotations(prime)
for n in rotations:
if isPrime(n) == False:
return []
return rotations

def generatePrimesUpTo(n):
# use sieve of Eratosthenes
a = [True] * n
a[0] = a[1] = False
for i in range(2, int(math.sqrt(n))+1, 1):
if a[i]:
j = i**2
while j < n:
a[j] = False
j = j + i
for x in range(len(a)):
if a[x]:
yield x

def getCircularPrimes(limit):
cPrimeList = []
for i in generatePrimesUpTo(limit):
if i > 9 and i not in cPrimeList:
# we haven't seen this prime or its rotations before
rotations = getCircularRotations(i)
if len(rotations) > 1:
print (rotations)
cPrimeList.extend(rotations)
elif len(rotations) == 1:
# this is a palindromic circular prime
print (i)
cPrimeList.append(i)
elif i==2 or i==3 or i==5 or i==7:
print (i)
cPrimeList.append(i)
return cPrimeList

limit = 1000000
print ('Number of circular primes under {}: {}'.format(limit, len(getCircularPrimes(limit))))
Project Euler Problem 46 – Goldbach’s other conjecture (Source)

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Language: Python 3
#!/usr/bin/python3
import math

def generatePrimesUpTo(n):
# use sieve of Eratosthenes
a = [True] * n
a[0] = a[1] = False
for i in range(2, int(math.sqrt(n))+1, 1):
if a[i]:
j = i**2
while j < n:
a[j] = False
j = j + i
for x in range(len(a)):
if a[x]:
yield x

def checkComposite(composite, primes):
# check (prime + 2*squareBase^2) == composite and try to find a solution
# if there's a solution, return a set containing [prime, square]
# otherwise, return an empty set
for prime in primes:
squareBase = 1
# increment squareBase until prime + 2*squareBase^2 >= composite
while prime + 2 * math.pow(squareBase, 2) <= composite:
if prime + 2 * math.pow(squareBase, 2) == composite:
# we have a solution
print ('solution for {} == {} + 2 * {}^2'.format(composite, prime, squareBase))
return False
else:
squareBase += 1
# if we got here then there's no solution
print ('Found no solution for: {}'.format(composite))
return True

def checkOddCompositeNumbers(limit):
primeList = list(generatePrimesUpTo(limit))
# check all odd numbers from n=5 to the last prime in the list
for n in range(5, primeList[len(primeList)-1], 2):
# any number larger than 1 which isn't prime is a composite
if n not in primeList:
# filter the list to all primes < n, then reverse the order
# this means the largest prime < n will be at the 0 index
candidates = list(filter(lambda x : x < n, primeList))[::-1]
if checkComposite(n, candidates):
return

checkOddCompositeNumbers(10000)
Project Euler Problem 47 – Distinct primes factors (Source)

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

Language: Python 3
#!/usr/bin/python3
import math
def generatePrimesUpTo(n):
# use sieve of Eratosthenes
a = [True] * n
a[0] = a[1] = False
for i in range(2, int(math.sqrt(n))+1, 1):
if a[i]:
j = i**2
while j < n:
a[j] = False
j = j + i
for x in range(len(a)):
if a[x]:
yield x

def findFactors(target, desiredFactors, primeList):
# populate a list with all prime numbers which evenly divide target
divisors = []
n = 0
while primeList[n] < target and n < len(primeList)-1:
if target % primeList[n] == 0:
# print ('{} is a factor of {}'.format(primeList[n], target))
divisors.append(primeList[n])
n += 1
return divisors


def findConsecutives(dconsec, dfactors, primeLimit):
primeList = list(generatePrimesUpTo(primeLimit))
consecutives = []
n = 1
# search for `dconsec` consecutive numbers with `dfactors` number of distinct prime factors
while len(consecutives) < dconsec and n < math.pow(primeList[len(primeList)-1], 2):
# only bother to calculate factors for numbers we know are not primes
if n not in primeList:
factors = findFactors(n, dfactors, primeList)
else:
factors = []

if len(factors) >= dfactors:
# we found a match, add it to the list
# print ('found {} distinct factors for {}: {} (streak: {})'.format(len(factors), n, factors, len(consecutives)))
consecutives.append([n, factors])
elif len(consecutives) > 0:
# streak broken, clear the list
consecutives = []
n += 1
if len(consecutives) == dconsec:
print ('Success: {}'.format(consecutives))
else:
print ('Failed to find enough consecutives. Try increasing prime limit')

# findConsecutives(2, 2, 800)
# findConsecutives(3, 3, 800)
findConsecutives(4, 4, 800)