Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Welcome to Software Development on Codidact!

Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.

Current solution for Project Euler 250+ (HackerRank) is giving incorrect answers, why is this?

+2
−0

Note: I originally posted this on Stack Overflow on Stack Exchange here however I am posting the same question here as I might be able to get a answer more quickly here.


Project Euler+ #250 on HackerRank is as follows:

Find the number of non-empty subsets of $\{1^1, 2^2, 3^3,..., n^n\}$, the sum of whose elements are divisible by $k$. Print your answer modulo $10^9$

You can find this here.

The constraints are as follows:

$$\begin{align}1\le&\;n\le10^{400}\\3\le&\;k\le50\end{align}$$

I originally posted a Code Review question here, but I have since modified my solution after taking a 2-month break from HackerRank and after solving the original problem on Project Euler.


Here is my current code (using Python 3.12):

from math import lcm

MOD = 10 ** 9

def phi(n):
    c = 2
    s = n
    while n > 1:
        if n % c == 0:
            s -= s // c
        
        while n % c == 0:
            n //= c
        
        c += 1
    
    return s

def compute(N, n, m = MOD):
    cycle = lcm(n, phi(n))
    # A guess for what the period for `i ** i % k` will be.
    
    def convolve(A, B):
        return [sum(a * b for a, b in zip(A, B[i::-1] + B[:i:-1])) % m for i in range(n)]
    
    q, rem = divmod(N, cycle)
    A = end = [1] + [0] * (n - 1)
    for i in range(1, cycle + 1):
        k = pow(i, i, n)
        A = [(a + b) % m for a, b in zip(A, A[-k:] + A[:-k])]
        if i == rem:
            end = A
    
    base, A = A, [1] + [0] * (n - 1)
    for j in bin(q)[2:]:
        A = convolve(A, convolve(A, base) if j == '1' else A)
    
    A = convolve(A, end)
    return (A[0] - 1) % m
#---------------------------------------------------------------
n, k = map(int, input().split())
print(compute(n, k))

However, this does not solve all 56 test cases. In fact, for all 9 test cases I don't solve (those being hidden test cases 11, 16, 17, 20, 23, 28, 32, 52, 53), I am getting incorrect answers.


My question is: What is wrong with my code that is causing me to get incorrect answers, and how could I possibly fix this?

Something tells me that it has either to do something with my guess for the cycle parameter for some values of $k$, or maybe the problem is with how I am computing the convolutions, but I'm not really sure.

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

Non-empty? (2 comments)

0 answers

Sign up to answer this question »