3 kyu

N-Parasitic Numbers Ending in N

449 of 967LesRamer

Description:

This challenge is to compute a special set of parasitic numbers for various number bases.

An n-parasitic number (in base 10) is a positive natural number which can be multiplied by n by moving the rightmost digit of its decimal representation to the front. Here n is itself a single-digit positive natural number. In other words, the decimal representation undergoes a right circular shift by one place. For example, 4 • 128205 = 512820, so 128205 is 4-parasitic

Special Parasitic Numbers

For some N there may be multiple N-parasitic numbers. This Kata is concerned with finding a special set of n-parasitic numbers where the trailing digit is also the 'N' in the N-parasitic number. In base-10, the above Wikipedia excerpt shows that 128205 is 4-parasitic since 4 • 128205 = 512820; however, the special number this Kata is looking for is the smallest 4-parasitic number that also ends in 4, which is 102564: 4 • 102564 = 410256.

A Clarifying Anti-Example

The "ending in N" portion of the requirements seems easily missed. While 5 • 142857 = 714285, this 142857 number is parasitic but it is not the number sought by this kata because it ends with a 7 in the ones' place rather than 'n' (which is 5 in this case).
         v--- kata requires this digit to be 5 for n = 5
5 • 142857 = 714285
             ^--- kata requires this digit to be 5 for n = 5

While the product happens to end with a 5 in the one's place, that ends-with-N requirement is on the multiplicand not on the product. The answer sought is much bigger than 142857 for n = 5.

Challenge

Provide a method accepting two arguments: the special trailing digit and a number base. Your method should return the string representation of the smallest integer having the special parasitic number property as described above in the requested number-base (octal, decimal and hex.) Each number base will test for all trailing digits other than 0 and 1, giving a total of 28 test cases.

Why the smallest?

Consider how the special 4-parastic HEX number ending in 4 is 104.

104 Hex • 4 = 410 Hex.

Repeating 104 twice and multiplying by 4 gives us 104104 Hex • 4 = 410410 Hex. This property holds regardless of how many times the set of digits is repeated (e.g., 104104 Hex • 4 = 410410 Hex, 104104104 Hex • 4 = 410410410 Hex, 104104104104 Hex • 4 = 410410410410 Hex, ...), leading to an infinite set of these special numbers in each case. Your task is to find only the smallest number that satisfies the special parasitic property. [This fact is a hint on one possible way to solve this problem.]

Hints:

  • Unless you can be clever about it, brute force techniques probably won't work.
  • An answer exists satisfying the criteria for each of the trailing-digits tested.
  • Leading zero-digits are not allowed.
  • Test failures will reveal the inputs rather than the expected value.

After you have solved it:

Can you find two other algorithmically different approaches to solve this puzzle? The refrence solutions in JavaScript, C# and Python solve the puzzle in fundamentally different ways.

Algorithms
Mathematics
Puzzles

Stats:

CreatedAug 27, 2015
PublishedAug 28, 2015
Warriors Trained9056
Total Skips4635
Total Code Submissions11067
Total Times Completed967
C# Completions107
Java Completions147
JavaScript Completions194
Ruby Completions69
Python Completions449
COBOL Completions7
Go Completions19
Rust Completions40
D Completions7
Total Stars247
% of votes with a positive feedback rating92% of 177
Total "Very Satisfied" Votes156
Total "Somewhat Satisfied" Votes15
Total "Not Satisfied" Votes6
Total Rank Assessments10
Average Assessed Rank
3 kyu
Highest Assessed Rank
2 kyu
Lowest Assessed Rank
5 kyu
Ad
Contributors
  • LesRamer Avatar
  • smile67 Avatar
  • user8436785 Avatar
  • akar-0 Avatar
  • Twilight_Sun Avatar
  • saudiGuy Avatar
Ad