<!DOCTYPE html>
<html ng-app="ulamApp">
<head>
<title>Ulam Spiral Generator</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link data-require="bootstrap-css@*" data-semver="3.3.1" rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.1/css/bootstrap.min.css" />
<script data-require="lodash.js@*" data-semver="3.1.0" src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/3.1.0/lodash.min.js"></script>
<script data-require="angular.js@*" data-semver="1.4.0-beta.5" src="https://code.angularjs.org/1.4.0-beta.5/angular.js"></script>
</head>
<body ng-controller="ulam" ng-cloak>
<div class="container-fluid">
<div id="col" class="col-xs-12 col-sm-8 col-sm-offset-2 col-md-6 col-md-offset-3 col-lg-4 col-lg-offset-4">
<h2>Ulam Spiral Generator</h2>
<h4>v 0.1.2</h4>
<hr>
<form ng-hide="dataUri"
ng-submit="generate(max, width)">
<legend>Max number of dots</legend>
<div class="form-group">
<label>Preset</label>
<br>
<div class="btn-group btn-group-justified" role="group">
<div class="btn-group">
<button type="button"
ng-click="max = 100"
class="btn btn-default btn-success">100</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="max = 1000"
class="btn btn-default btn-success">1k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="max = 10000"
class="btn btn-default btn-warning">10k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="max = 50000"
class="btn btn-default btn-warning">50k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="max = 100000"
class="btn btn-default btn-danger">100k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="max = 1000000"
class="btn btn-default btn-danger">1m</button>
</div>
</div>
</div>
<div class="form-group">
<label>Custom</label>
<br>
<input type="number"
class="form-control"
ng-model="max"
ng-init="max = 10000"
placeholder="Maximum">
</div>
<legend>Resolution</legend>
<div class="form-group">
<label>Preset</label>
<br>
<div class="btn-group btn-group-justified" role="group">
<div class="btn-group">
<button type="button"
ng-click="width = 1920"
class="btn btn-default btn-success">1080p</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="width = 2048"
class="btn btn-default btn-success">2k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="width = 4096"
class="btn btn-default btn-warning">4k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="width = 5120"
class="btn btn-default btn-warning">5k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="width = 6144"
class="btn btn-default btn-danger">6k</button>
</div>
<div class="btn-group">
<button type="button"
ng-click="width = 7680"
class="btn btn-default btn-danger">8k</button>
</div>
</div>
</div>
<div class="form-group">
<label>Custom Width/Height</label>
<input type="number"
class="form-control"
ng-model="width"
ng-init="width = 1920"
placeholder="Output Width">
</div>
<div class="form-group">
<button type="submit"
class="btn btn-lg btn-block btn-primary">Generate</button>
</div>
</form>
<div ng-show="dataUri">
<button ng-click="dataUri = undefined"
class="btn btn-lg btn-block btn-primary">Change Output</button>
<br>
<a id="download"
download="ulam.png"
class="btn btn-lg btn-block btn-success">Download at Full Resolution</a>
<br>
<h4>Low-res Preview</h4>
<img style="width: 100%"
ng-src="{{dataUri}}" alt="ulam spiral preview" />
</div>
<hr>
<a href="README.md" class="pull-left"><h5>README</h5></a>
<h5 class="pull-right">© {{date | date:'yyyy'}} <a target="_blank" ng-href="https://github.com/BrainBacon">Brian Jesse</a></h5>
</div>
</div>
<script src="script.js"></script>
</body>
</html>
/*
* License for images generated by this code: Attribution 4.0 International (https://creativecommons.org/licenses/by/4.0/)
* License for this code: Attribution-NonCommercial-ShareAlike (https://creativecommons.org/licenses/by-nc-sa/4.0/)
* See README.md for more information
*/
angular.module('ulamApp', []).controller('ulam', function(
$scope
) { 'use strict';
$scope.date = new Date();
$scope.generate = function(max, width) {
// Generate Ulam Spiral
var spacing = width / Math.sqrt(max);
var nums = divcount(max);
var circles = drawCircles(_.max(nums), spacing);
var output = draw(max, width, nums, spacing, circles);
// Download link
var outputUri = output.toDataURL('image/png');
outputUri = outputUri.substring(outputUri.indexOf(',') + 1);
var byteCharacters = atob(outputUri);
var byteNumbers = new Array(byteCharacters.length);
for (var i = 0; i < byteCharacters.length; i++) {
byteNumbers[i] = byteCharacters.charCodeAt(i);
}
var byteArray = new Uint8Array(byteNumbers);
var blob = new Blob([byteArray], {type: 'application/octet-stream'});
var download = document.getElementById('download');
download.href = URL.createObjectURL(blob);
// Thumbnail
var canvas = document.createElement('canvas');
var container = document.getElementById('col');
canvas.width = container.offsetWidth;
canvas.height = container.offsetWidth;
var context = canvas.getContext('2d');
context.drawImage(output, 0, 0, container.offsetWidth, container.offsetWidth);
$scope.dataUri = canvas.toDataURL('image/png');
$scope.generated = true;
};
// count the number of divisors for each number up to max
function divcount(max) {
var out = [];
for(var l = 0; l <= max; l++) {
out.push(0);
}
var k = Math.floor(Math.sqrt(max));
for(var i = 1; i <= k; i++) {
out[i * i]++;
for(var j = Math.floor(max / i); j > i; j--) {
out[i * j] += 2;
}
}
return out;
}
// Precompute each possible circle size - HUGE performance gains
function drawCircles(max, spacing) {
var circles = [];
for(var i = 1; i < max + 1; i++) {
var tmpCanvas = document.createElement('canvas');
tmpCanvas.width = 2 * spacing;
tmpCanvas.height = 2 * spacing;
var tmpContext = tmpCanvas.getContext('2d');
tmpContext.beginPath();
tmpContext.arc(
spacing,
spacing,
spacing * (i / max),
0, 2 * Math.PI,
false
);
tmpContext.fillStyle = '#FFFFFF';
tmpContext.fillStyle = 'hsla(' + 359 * (i / max) + ',100%,50%,1.0)';
tmpContext.fill();
circles[i] = tmpCanvas;
}
return circles;
}
// Main draw function
function draw(max, width, nums, spacing, circles) {
// Set up canvas
var canvas = document.createElement('canvas');
canvas.width = width;
canvas.height = width;
var context = canvas.getContext('2d');
// Draw background
context.fillStyle = '#000000';
context.fillRect(0, 0, canvas.width, canvas.height);
// Set up spiral
var centerX = Math.floor(canvas.height / 2);
var centerY = Math.floor(canvas.height /2);
var minX = centerX;
var minY = centerY;
var maxX = centerX;
var maxY = centerY;
var curX = centerX;
var curY = centerY;
// spiral outwards
for(var i = 1; i < max; i++) {
// Get a dot
context.drawImage(circles[nums[i]], curX - (Math.ceil(spacing / 2)), curY - (Math.ceil(spacing/2)));
if(curY <= maxY && curX > maxX) {
// v
if(curY < minY) {
minY = curY;
}
curY += spacing;
} else if(curX >= minX && curY > maxY) {
// <
if(curX > maxX) {
maxX = curX;
}
curX -= spacing;
} else if(curY >= minY && curX < minX) {
// ^
if(curY > maxY) {
maxY = curY;
}
curY -= spacing;
} else {
// >
if(curX < minX) {
minX = curX;
}
curX += spacing;
}
}
return canvas;
}
});
# Ulam Spiral Generator
## About
* This software will generate a [Ulam Spiral](http://en.wikipedia.org/wiki/Ulam_spiral) with both prime and composite numbers drawn.
* Dots are color-coded and proportionally sized based on the number of divisors of the number at the drawn index.
### Algorithm to Generate Divisor Counts
* The algorithm works best when using larger ranges of numbers instead of calculating a single numbers divisor count.
* It runs in O(sqrt(n)*log(n)) time.
* It works on a simple principle: instead of starting from the top, picking a number, and calculating its factors it starts from the bottom i.e. taking two unique factors, multiplying them, and adding both factors to a result number in the range we wish to calculate.
* The set of unique factor combinations was easily reduced since the outer loop will run factors up to the square root of the max starting at the minimum, and the inner loop will multiply by the factors starting with the max and counting down until it gets to the factor that is currently being run by the outer loop.
* If the outer loop ran past the square root of the max then the result would be greater than the max, and if the inner loop calculated less than the factor currently being calculated in the outer loop then that combination has already been calculated.
prime numbers have 2 divisors, 1 and themselves, any other number will count the number of factors, e.g. 12 is divisible by 6 numbers (1,2,3,4,6,12).
The function `divcount(max)` will calculate all divisor counts between 0 and max.
Example:
```
divcount(12);
[0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6]
```
### Drawing Algorithm
* Circles are precomputed using many additional canvas objects and appended to the main canvas with `drawImage()`.
* The main draw function will draw circles spiraling outwards starting from the center.
* The draw function will output a dataUri and append it as an image to the document.
## Use
1. Select the number of dots generated in the spiral using one of the presets or a custom integer value.
2. Select the output resolution of the image that will be generated using one of the presets or a custom integer value.
3. Click Generate.
4. An image preview will be displayed below the generate button.
5. You may choose to save your image using the generated preview.
### Caveats
* Official support only for Chrome and Firefox
* Downloading may not work in older browsers, Safari, iOS, or IE
* Presets are color-coded according to the amount of processing and space required.
## License
License for images generated by this code
* [Attribution 4.0 International](https://creativecommons.org/licenses/by/4.0/)
License for source code
* [Attribution-NonCommercial-ShareAlike](https://creativecommons.org/licenses/by-nc-sa/4.0/)