5 kyu
Right Truncatable Harshad numbers
57 of 90anter69
Loading description...
Mathematics
Number Theory
Algorithms
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
You've surely enough got to come up with a way to pass the tests given the high constraints, that's why it's challenging and I liked solving it.
Could use tag:
number theory
done
This comment has been hidden.
Hint: precalculation / cache
This comment has been hidden.
The code gives out the final list with the Harshad numbers but it gives the execution runtime error. Please help.
Elixir translation awaiting approval.
Thanks!
👉😎👉
A nice kata, but it's a shame that runtime for Python is so slow. I initially wrote my solution in Python which would not pass due to timeout, but the exact same algorithm in JS yields a successful completion in 2 seconds.
Im sorry. Solution, which i submitted, is bad and too large. Because of this, my (and probably not only mine) browser crashes when I open solutions in this kata and "my solutions" in account. I dont know, how to solve this problem. I wish i could remove this solution, but, as I know, this is unavail.
I'm afraid there is not much to do about it... :-(
For some reason, my code works perfectly on my laptop's terminal but gets timed out here. Why?
Have you tried pouring coffee into your keyboard?
With the information you give, that's about the best advice I can give. That should make them perform the same again.
Seriously: post your code ( marked up and spoilered ). Right now, we don't even know what language you're using.
LOL.
JavaScript translation
Note:
b
limited toNumber.MAX_SAFE_INTEGER
(2**53 - 1 ~ 9e15
); description updated for JavaScript.Thanks
Haskell:
Should be fixed. Don't forget to reload.
Is it fixed?
Haskell translation
Thanks! (hoping it's good :-)
Yeah, I hope so too! :ROFL:
Working on JavaScript now.
I guess not
I developed with
Integer
s ( and bigger numbers ), then changed allInteger
s toInt
s - but I forgot the initial code.And I only tested the initial code against the example tests.
Still have the feeling that this upper bound may be too low for a 5 kyu kata :-P
Yes, the limit could be set higher (at least 10^20, easily), but the idea is to exclude naive solutions. It may be a bit easy for 5 kyu, although there is not much difference between 5 & 6, right?
Fun kata. I think the description is refreshingly nice and clear so kudos. Unfortunately I haven't thought up a fast enough implementation yet :P
Thanks for the compliment, and keep thinking! :-)
Exhaustive enumeration takes too much time for big numbers, so cannot pass through random test (timeout).
Then you need to change your approach, as it's (easily) doable for even bigger numbers.
Kind of tough for a 5 kyu (because of performance requirements). But fun!
I find 5 kyu about right. Oh, and thanks for the compliment!
I think this is a tough kyu 5 ;)
The kata has become approvable, so I think I should reopen the issue. See below.
As I explained below already, the result of the truncation has to be a Harshad number (not a right-truncatable Harshad number). If you can "successfully" repeat the truncation (=the result is a Harshad number), then it's a right-truncatable Harshad number.
For me it sounds clear (I took the description directly from Project Euler), but help me reformulate it to make it more clear.
It doesn't really matter if the result doesn't have to be truncatable, all truncations of 1-digit numbers are Hashad numbers.
What exactly is not a number? It can't be truncated at all, so there's no result of a signle truncation at all, thus the result of recursive truncations is an empty sequence and it contains only Harshad number.
OK everyone, how about this?
Is it different somehow from what it was? Replacing
201
with2
: ...2
is a Harshad number ...Truncating...(2
cannot be truncated anymore.) Thus2
is a right truncatable Harshad number.I believe yes:
Can you truncate
2
? Does it yield a Harshad number?You know, you can just limit the lower bound to have
10 <= a
, and this wouldn't be relevant anymore ;-)One time - questionable (0 is a weird number that acts like a 0-digit number, but is often represented by 1 digit), recursively - you can and it results in a sequence of Harshad numbers.
Thanks for your feedback. Description updated, stating that 1-digit numbers are excluded.
Where are 1, 2, 3, 4, 5, 6, 7, 8, 9?
see below
How is it resolved??? If it's literally "always results in a Harshad number", then no number is truncatable because there's 0 in the end. Assuming that it applies to the numbers before 0 exclusively, 1-digit numbers are truncatable because there's no non-Harshad numbers in the sequence.
mmmm... correct.
Well, if you truncate a 1-digit number, there is nothing left (~ an empty "string"; not zero!). As "nothing" is not a number, you don't have to check/worry, if it's a Harshad number or not...
Description updated.
Correct, but this exactly means that a 1-digit number is truncatable. All numbers in the sequence are Harshad numbers (because the sequence is empty), in other words there's no non-Harshad number in the sequence.
You either have to define single-digit Harshad numbers as right-truncatable or you have to redefine right-truncatable Harshad numbers. As they are defined now, there are no right-truncatable Harshad numbers, because any number, right-truncated enough times, ends up being a single-digit number; which you have defined as non-right-truncatable.
Consider 201, given as an example in the description:
The result of the truncation has to be a Harshad number (not a right-truncatable Harshad number). If you can "successfully" repeat the truncation (=the result is a Harshad number), then it's a right-truncatable Harshad number.
For me it sounds clear (I took the description directly from Project Euler), but help me reformulate it to make it more clear.
This is the part that lead to confusion for me. I can see why it means what you say, but it wasn't my interpretation. On Project Euler, the last bit is italicized, which I think helps set it apart as a definition. At the least, a comma should be added, but a rephrasing may be in order.
We are really talking about recursive Harshad numbers ending with a single-digit number (which are Harshad numbers, but we can't just stop recursion at any Harshad number). Arguably the definition allows us to recurse "past" the single-digit number into undefined territory. The end point might as well be explicit.
So you might say something like:
I think this jibes with your definition and is also explicit about the end point, while avoiding ambiguity (or even caring) about how single-digit Harshad numbers are defined.
But, I will also add that defining single-digit numbers as non-truncatable is not particularly useful, makes the recursion weird (we look for Thing until we find Another Thing Entirely), and is not how other truncatable numbers are defined. Note that
2
is a truncatable prime[0] in both directions. So my true suggestion would be to define single-digit numbers (other than zero) as right-truncatable Harshad numbers.[0] https://en.wikipedia.org/wiki/Truncatable_prime#Lists_of_truncatable_primes
Thanks for your feedback. Description updated, stating that 1-digit numbers are excluded.
[30,100]
EDIT:
And you should make it
clearexplicit that values below 10 are Harshad numbers but are not truncatable, so they aren't in the sequence.Thanks for your feedback!
(30, 100)
,(90, 200)
,(1000, 2000)
);I just realize that I could have made it a little bit more difficult by including left truncatable numbers as well ;-)
Cheers
Yes, but the main interest of the random tests in this type of kata is to get a wuick check of your code. So maybe comment out that test so that the sample tests are runnable without perf requirements, but the user still gets the info about the expected range?
Thanks for the approval!