cubes

Some experiments with numbers that are cubes

How to use this?

Satisfy Dependencies

Following are essential:

• Git
• Gradle
• Scala
• Java SE 7

It is recommended to also use the following for experimenting with the source code:

• IntelliJ

Get the source and artifacts from Github

1. git clone https://github.com/cganoo/cubes.git
2. cd cubes/

Run Unit Tests

1. gradle check
2. gradle test -i
3. A nice html page showing unit test results will be available at ./build/reports/tests/index.html

Highlights

• Application description: A stand-alone scala app
• Build and Dependency management: Gradle is used for this
• Algorithms used: See below
• Unit Tests: A few representative Junit4 unit tests are included.

Notes on algorithms used

Find smallest cube for which exactly k permutations of its digits are cubes

• Finding cuberoots is more difficult than finding cubes
• So we can memoize and start calculating cubes of all numbers from 1 to some upper limit
• For each such cube that we calculate, the digits that constitute it can be used for identifying permutations
• CodePoint identification: Compute histogram for digits 0-9 and the resulting number is the codepoint. For example: codePoint(1252) = 0120010000
• FingerPrint identification: Sort the digits. For example: fingerprint(1225L) = 1225
• Leverage the cache used for memoizing to maintain cubes that yield the same codePoint/fingerPrint
• Scan the cache to find desired length groups of cubes and return smallest amongst them
• Upper limits are heuristics. For example for k = 3, an upper limit of 1000 is ok to find smallest cube (345).

License

cubes is licensed under the MIT license. It is primarily intended for fun and instructive purposes. Use this at your own risk.

Author

Chaitanya Ganoo www.linkedin.com/in/cganoo