<< problem 127 - abc-hits | Repunit divisibility - problem 129 >> |

# Problem 128: Hexagonal tile differences

(see projecteuler.net/problem=128)

A hexagonal tile with number 1 is surrounded by a ring of six hexagonal tiles, starting at "12 o'clock" and numbering the tiles 2 to 7 in an anti-clockwise direction.

New rings are added in the same fashion, with the next rings being numbered 8 to 19, 20 to 37, 38 to 61, and so on. The diagram below shows the first three rings.

By finding the difference between tile n and each of its six neighbours we shall define PD(n) to be the number of those differences which are prime.

For example, working clockwise around tile 8 the differences are 12, 29, 11, 6, 1, and 13. So PD(8) = 3.

In the same way, the differences around tile 17 are 1, 17, 16, 1, 11, and 10, hence PD(17) = 2.

It can be shown that the maximum value of PD(n) is 3.

If all of the tiles for which PD(n) = 3 are listed in ascending order to form a sequence, the 10th tile would be 271.

Find the 2000th tile in this sequence.

# My Algorithm

Tile 1 matches all conditions: PD(1) = 3 because 4-1=3 is prime, 3-1=2 is prime and 6-1=5 is prime.

Tile 2 matches all conditions: PD(2) = 3 because 9-2=7 is prime, 19-2=17 is prime and 7-2=5 is prime.

My first program performed that task for all numbers from 1 to 1000. It didn't find the solution because surprisingly only a tiny fraction of tiles matches all conditions.

Then I looked at tile 17 more closely:

- its predecessor and its successor are neighbors, their difference is 1 which is not a prime

- on its left side (the ring inside) there are the two consecutive numbers 6 and 7. Only one difference is odd, the other is even (can't be a prime)

- on its right side (the ring outside) there are the two consecutive numbers 33 and 34. Only one difference is odd, the other is even (can't be a prime)

Without computing the differences 17-6, 17-7, 33-17 and 34-17 I know that at most two difference can yield a prime number.

In general, every number located on the edge/side of a ring has PD(x) <= 2. Therefore 9, 11, 13, 15, 17, 21, 22, 24, 25, 27, 28, ... can be excluded.

Note that there is a single exception: the last tiles of each ring (7, 19, 37, ...) have no connection to their successors. They remain candidates for PD(x) = 3.

Now only the numbers on the "corners" of each ring are left (such as 2,3,4,5,6,7,8,10,12,14,16,18,20,23,26,...).

Except for the corners "north" of 1 (2,8,20,..., they are the first numbers of a ring), each of those tiles is connected to its predecessor and its successor (remember: difference is 1 → no prime).

The neighbors on the outside ring are three consecutive numbers. Only if the difference to the first and the last of these three tiles is odd, then at most two differences can be prime.

For PD(x)=3, the inner tile must be prime, too. That means either the two relevant outer and the inner tile are odd while the corner tile is even or

the two relevant outer and the inner tile are even while the corner tile is odd.

The inner tile is a corner tile, too, and has the difference 6*ring + corner (where 1 <= corner <= 5, I look at the "north" tile later).

Clearly, the second and fourth corner have always an even difference and their PD(x) must be smaller than 3.

The middle of the outer three tiles is a corner tile as well and has a difference of 6*(ring+1) + corner.

Obviously, its predecessor and successor have a difference of 6*(ring+1) + corner \pm 1.

The first, third and fifth corner produce an even difference which is never prime.

These formulas are a bit off for the first 7 tiles because my formulas 6*ring and 6*(ring+1) are valid everywhere - but not in the centre.

I manually inspected the first seven tiles and found that only tiles 1 and 2 match all conditions.

The only tiles left are the first and last tiles of each ring. My program checks their surrounding tiles, or better say, their differences.

The difference between the first tile of the current ring and the first tile of the previous ring is `incrementFrom = (ring - 1) * 6`

(where `ring`

denotes the current ring).

The difference between the first tile of the current ring and the first tile of the next ring is `incrementTo = ring * 6`

.

And the difference between the first tile of the current ring and the ring beyond the next ring is `incrementTo2 = (ring + 1) * 6 + incrementTo`

.

There are six tiles around the first tile of ring and their differences are (beginning from the bottom at 6 o'clock, 8 o'clock, 10 o'clock, ..., 4 o'clock):

`a = incrementFrom`

→ multiple of 6, never prime

`b = 1`

→ never prime

`c = incrementTo + 1`

`d = incrementTo`

→ multiple of 6, never prime

`e = incrementTo2 - 1`

`f = incrementTo - 1`

Only three tiles are actual candidates (`c`

, `e`

and `f`

).

There are six tiles around the last tile of ring and their differences are (same order as first tile):

`a = incrementTo`

→ multiple of 6, never prime

`b = incrementFrom + incrementTo - 1`

`c = incrementTo - 1`

`d = incrementTo2 - incrementTo`

→ multiple of 6, never prime

`e = incrementTo2 - incrementTo - 1`

`f = 1`

→ never prime

Only three tiles are actual candidates (`b`

, `c`

and `e`

).

One difference appears for both tiles (`incrementTo - 1`

). My program checks this difference first for a small performance gain.

## Note

The upper limit of my prime sieve was determined by running the program a few times and counting which primes where checked

(by the way: I used the Miller-Rabin primality test but it is magnitudes slower than the current primitive sieve).

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

The code contains `#ifdef`

s to switch between the original problem and the Hackerrank version.

Enable `#ifdef ORIGINAL`

to produce the result for the original problem (default setting for most problems).

#include <iostream>
#include <vector>
// standard prime sieve, see my toolbox
// odd prime numbers are marked as "true" in a bitvector

std::vector<bool> sieve;
// return true, if x is a prime number

bool isPrime(unsigned int x)
{
// handle even numbers
if ((x & 1) == 0)
return x == 2;
// lookup for odd numbers
return sieve[x >> 1];
}
// find all prime numbers from 2 to size

void fillSieve(unsigned int size)
{
// store only odd numbers
const unsigned int half = size >> 1;
// allocate memory
sieve.resize(half, true);
// 1 is not a prime number
sieve[0] = false;
// process all relevant prime factors
for (unsigned int i = 1; 2 * i*i < half; i++)
// do we have a prime factor ?
if (sieve[i])
{
// mark all its multiples as false
unsigned int current = 3 * i + 1;
while (current < half)
{
sieve[current] = false;
current += 2 * i + 1;
}
}
}
int main()
{
// fill a prime sieve (maximum prime was determined by running it a few times)
#define ORIGINAL
#ifdef ORIGINAL
unsigned int limit = 2000;
fillSieve(835000);
#else
unsigned int limit = 80000;
fillSieve(91200000);
#endif
// [nth number] => [tile]
std::vector<unsigned long long> found = { 1, 2 };
// tiles 1 and 2 are the first two tiles because PD(1)=PD(2)=3
unsigned int numFound = 2;
// and there are no further tiles below 8 where PD(x)=3
unsigned long long first = 8;
// analyze rings until enough numbers are found
for (unsigned long long ring = 2; numFound < limit; ring++)
{
// difference to previous ring (inside current ring)
auto incrementFrom = (ring - 1) * 6;
// difference to next ring (outside current ring)
auto incrementTo = ring * 6;
// difference to ring after the next ring
auto incrementTo2 = (ring + 1) * 6 + incrementTo;
// difference "incrementTo - 1" appears twice: around first and last tile
if (!isPrime(incrementTo - 1))
{
first += incrementTo;
continue;
}
// check first number of a ring
if (isPrime(incrementTo + 1) && isPrime(incrementTo2 - 1))
{
numFound++;
found.push_back(first);
}
// check last number of a ring
if (isPrime(incrementFrom + incrementTo - 1) && isPrime(incrementTo2 - incrementTo - 1))
{
numFound++;
auto last = first + incrementTo - 1;
found.push_back(last);
}
// next ring
first += incrementTo;
}
// look up results
unsigned int tests = 1;
std::cin >> tests;
while (tests--)
{
unsigned int index = 2000;
std::cin >> index;
std::cout << found[index - 1] << std::endl;
}
return 0;
}

This solution contains 17 empty lines, 25 comments and 6 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "1 10" | ./128`

Output:

*Note:* the original problem's input `2000`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

June 24, 2017 submitted solution

June 24, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler128

My code solves **9** out of **9** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **55%** (out of 100%).

Hackerrank describes this problem as **hard**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

# Links

projecteuler.net/thread=128 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 127 - abc-hits | Repunit divisibility - problem 129 >> |