Factoring semiprimes using only addition

Methodology:

  1. Create a dictionary. Add keys for all primes below the square root of the semiprime (or just odd numbers, if you don’t have a list of the primes), and set the value to be the same as the key
  2. For each dictionary entry — add the key to the value
  3. If the value == semiprime — then factor found
  4. If the value > semiprime — then remove this dictionary entry and all dictionary entries with a higher key
  5. Repeat until factor found

Why does this work?

Simply put, the semiprime is the product of two primes. For example — 3 * 7 = 21.  As such — 7 lots of 3’s (3+3+3+3+3+3+3) and 3 lots of 7’s (7+7+7) = 21. All day, every day.

Is it a fast way to factor semiprimes?

Nope. Not even close. It’s just a mathematical constraint-based curiosity — and I like those 🙂

Apparently, it’s my Birthday

I am now officially old enough to use the phrase “Get off my lawn”. Also — “I’d have got away with it, too, if it wasn’t for you darn kids!”

To celebrate, I’m breaking out the Brandy.

Cheers 🙂

How to have Less ads (and fund the Internet).

Adverts suck.

They make every user experience on the Internet worse. They’re also a vector for virus injection.

Users already hate them, as illustrated by the popular rise of ad blockers.

So — here’s a modest proposal for a new funding model for the web:

User’s opt in to an ad-free internet service, that costs X per month. Let’s say $20.

Websites that support that service remove ads when users of that service use their site. In return, they receive a slice of that X per month.

Website providers get micro transactions per view; User’s get Ad-free websites.

Win/win, right?

Like the idea? Google are already trialling the concept here, for some sites running Google Ads.

Truth is, though — it’s bigger than Google. It could be used for funding websites, anywhere — including those that aren’t traditionally ad supported — such as Wikipedia, and even your auntie’s blog.

My spin on the concept? Use it to encourage quality content.

Reward stickiness. Rather than make it hit based, which encourages bad UX — make it into a time-spent based thing, instead.

Also, weight the payments by individual user rating — from 1/2 a star through to 5 star, so the users can reward perceived high quality sites and incentivize lower quality sites to improve.

There would need to be some significant buzz to get websites on board. Proposing HTML tags for Adverts (and opting out of them) might do it:

<advert optout=’adfree.com/authenticate’><img src=’./allthethings.jpg’></advert>

Get the browser to check to see if the user is authenticated for one of the current optout services (returns true or false). If so, remove the advert from the Dom, and send the optout service time spent info and the user’s current rating for the site on page exit.

And then, sites can choose to opt in to the no advert service, and serve ads for those they don’t support.

Alternatively — create a monolithic non-profit organization to run a single central optout service, staffed by volunteers from the major tech companies. The best single company to attempt this at the moment, imo, is probably Paypal, who already have the ability to debit money from bank balances and distribute that money to other Paypal accounts at (presumably) extremely low cost.

And once we’ve got adverts sorted — maybe we can do the same thing with subscription services, such as Netflix, Pandora et al. A pot of money shared between them all, based on their usage and rating.

 

Announcing: The Infectious Madness of Doctor Dekker

691937244_preview_dekkerprofilesteam5

Coding for the day job eats most of my time. But when I’m not doing that, I’m working on other things – for myself, and in collaboration with others.

That's what I do. I write and I code things.

That’s what I do. I write and I code things.

This one’s still in progress, and probably won’t be released until mid-next year, but I’m going to announce it early.

“The Infectious Madness of Doctor Dekker” is a Full Motion Video game with Lovecraftian themes. Think “Her Story” meets Cthulhu.

The game framework is being coded by me in Node.js and runs on Windows, OS/X and Linux. My brother and sister-in-law are working hard on producing the content.

It’s currently in Steam Greenlight concepts. Feel free to take a peek / vote / follow / fave.

Node.js

Javascript has won web scripting.

As such — I’m officially giving in to the darkside.

Javascript on the client. Javascript on the server. Javascript everywhere.

Why wrestle with multiple languages, when you can choose to just wrestle with one?

Node.js is now my new weapon of choice on the server for future personal projects. Runs on Windows, Linux and Mac. HTML5 browser for Web, Electron for Desktops, Cordova for Mobile.

Done.

Code Golfing – Smallest Multiple

Code Golfing is the art of taking some code and making it as small as you possibly can. Normally, it takes the form of a function and tests are run against it to make sure your code still works, after you’ve tweaked it for size.

I’ve avoided it, up until now, because other than a form of entertainment, it doesn’t have much useful function. In terms of production code – code that you can understand and easily maintain is much more useful than code that’s difficult to read, but smaller. Now that we’re in the age where it’s fairly normal to download 10gb patch files for games, aside from web pages, I can’t remember the last time I overly worried about the size of the source code.

Anyway. I tried some Code Golfing this weekend, and it’s actually quite fun. I learnt a couple of things, too about stuff I’d never try in production – like if you weld a for loop into an infinite one, by using a blank middle condition, then the compiler is intelligent enough to realise that anything which follows (including the usual default return) will never be reached.

Best of all – it got my brain sparking again.

The challenge I attempted was this one:

Given a positive integer n, find the first positive integer divisible by 2, 3, 5, and 7 with at least n digits. Return the result as a string, as n may be as up to 10³.

So, 1,000 digit numbers. The kind of territory I find fun.

I checked to see whether I could use the System.Numerics.Biginteger class. No such luck. At which point, the problem became how to easily cope with 1,000 digit numbers.

I could write my own Biginteger class, but that would take up a lot of characters. Being Code Golf, that would be a total no-no, but I could jury-rig something just for plain addition.

So, I quickly hacked together a couple of byte arrays to represent individual digits, started at 210 and just added 210 continually, testing to see if I ever reached n digits of use, and taking the result afterwards.

At which point, I ran nose-first into another Code Golf constraint: All solutions have to run in under a second.

While my solution was working and small, it certainly wasn’t fast – and it needed to be all three.

I realised that I needed a completely different approach – and what I ended up with, was this:

string smallestMultiple(int n) {
 // This solution uses several "Tricks".
 // The first "Trick" is realising that the number to be returned will always be
 // within 210 of 10 ^ n.
 
 // The second "Trick" relies on a combination of two divisibility rules, namely:
 
 // Anything divisible by 2 ends in 0,2,4,6, or 8
 // Anything divisible by 5 ends in 0 or 5
 
 // Combine those two rules, and it should be obvious that our number
 // must end with a 0. 
 
 // The third "Trick" is that for a number to be divisible by 3, the sum of all it's
 // digits must also be divisible by 3.
 // In combination with our first trick, for any numbers which have four digits or more,
 // we know that we will always have:
 // A 1, a number of zeros, and a number between 0 and 209.
 // Given that we know it must end in a zero, that leaves valid values for our number as:
 // 20, 50, 80, 110, 140, 170, or 200
 
 // The fourth "Trick" is that for a number to be divisible by 7, the sum of 
 // alternating sets of 3 digits from the right added and subtracted together
 // is also divisible by 7. So, again - for any number that has four digits or more,
 // the number we are looking for is going to look like this:
 //
 // Either: 1 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 // or: 10 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 // or: 100 + a number of zeros, and 20, 50, 80, 110, 140, 170, or 200
 //
 // Depending on how big n is. If n = 4, then it's 1, if n = 5 then it's 10,
 // n=6 = 100, n = 7 = 1 again (and 3 0's) etc.
 // 
 // We need to work out whether to add or subtract the 1, 10 or 100 to our
 // 20, 50, 80, 110, 140, 170, or 200 before testing by divisibility by 7.
 // If n=4-6, we subtract, if it's 7-9 we add, 10-12 we subtract, 13-15 we add, etc.
 // Note that because any other set of 3 digits are zero's, we can ignore them 
 
 // And now - to the code.
 
 // First off - for any number less than 1000 (n = 4), the answer is always
 // 210 (2 * 3 * 5 * 7)
 if (n < 4) return "210";
 
 // Work out if we're going to adjust the number by 100, 10 or 1. 
 int a = n % 3 == 0 ? 100 : n % 3 == 1 ? 1 : 10;
 
 // Work out if we should add or subtract that adjustment (1 is add, -1 is subtract)
 int b = n % 6 > 3 || n % 6 == 0 ? -1 : 1; 
 
 // Loop guesses starting at 20, adding 30 each loop
 for (int x=20;; x+=30)
 {
 
 // if our guess modified by the adjustment is divisible by 7 - then we have our answer.
    if ((x + a * b) % 7 == 0) return "1".PadRight(n - 3, '0')
       + x.ToString().PadLeft(3, '0');
 }

 // Note that there's no return here. Because our for statement is missing it's
 // conditional check to exit, the compiler's intelligent enough to know that it's
 // never going to get this far. As I *know* that I'm going to get an early hit, I can
 // get away with an infinite loop for code golfing purposes, but I'd never advise using
 // one in the real world, other than for tight game loops, etc.
}

In total – 194 characters (Comments aren’t counted). Fairly decent, I thought.

The shortest entry, however, was 104 characters. Looking at their code (you’re allowed to, afterwards), it seems that there’s a repeating pattern of results – curiously not including  140. (I’m sure there’s a good Maths reason for that. Just not sure what it is).

Anyway – I finished 6th overall. Not bad, but not 1st, obviously. Still – for my first code golf outing – pretty pleased with that.

On “Said”

There’s currently a bit of a hoo-hah about the word “said” – the hoo-hah being that its made its way onto at least one teacher’s list of words that should not be used by school children.

Instead, they’re urged to use what are referred to in the trade as said-bookisms. Words such as barked, howled,  demanded, cackled. The reason being that they’re more emotive.

“This is terrible,” John barked.
“Why would you think that?” cried Mary.
“Because he does,” growled Peter.

Why is this a problem? Because by the time you’ve learned that John has barked those words, you’ve already parsed them in your head. You then have to go back and re-imagine them as being barked.

Most of the time, “said” will work perfectly fine. It holds no emotional surprises. For speech attribution, it’s virtually punctuation. If you want to evoke emotion, you should clue the reader in the character’s emotion prior to the words that are spoken. For example:

John swept the test papers off his desk. “This is terrible.”
As the papers fluttered to the ground, Mary felt her stomach flip. “Why would you think that?”
Peter put his hand on Mary’s shoulder and then glared at John. “Because he does.”

Doe John actually bark “This is terrible”? Depends if you, the reader, thinks he does. What you may lose in precision, you gain in congruence. The real key to immersive writing is choosing your words so that the reader only needs to parse them once, in a forward direction.

The side-project

September just vanished in a blur. So did October. The new job’s eaten a lot of my time.

The side-project I mentioned last time? That’s now in progress. I know it’s a tease, but I’m sworn to secrecy. Details to follow,  hopefully sometime in the first quarter of next year, as soon as it’s out of secret Beta.

I’m currently desperately trying to ignore that NaNoWriMo starts this Sunday. First time in four years I won’t be participating, due to said side-project and work eating every available minute.

In the meantime – Happy Halloween, everyone 🙂