CODEWITHSUNDEEP
pythondictionary
Alec
Alec

Reputation: 9536

Check if any keys in a dictionary match any values

I'm trying to solve this problem:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

I came up with a dictionary that holds x:d(x) for all numbers 0 to 9999 like so:

sums = {x:sum(alecproduct.find_factors(x))-x for x,y in enumerate(range(10**4))}

Where alecproduct.findfactors is a function from my own module that returns a list of all the factors of a number

I'm not sure where to go from here, though. I've tried iterating over the dictionary and creating tuples out of each k-v pair like so:

for k,v in sums.items():
    dict_tups.append((k,v))

But I don't think this helps me. Any advice on how I can detect if any of the dictionary keys match any of the dictionary values?

Edit - My solution based on 6502's answer:

sums,ap = {x:sum(find_factors(x))-x for x,y in enumerate(range(10**4))}, []

for x in sums:
    y = sums[x]
    if sums.get(y) == x and x != y:
        ap.append(x)

print(ap)
print('\nSum: ', sum(ap))

Upvotes: 2

Views: 97

Answers (4)

Elias Schoof
Elias Schoof

Reputation: 2046

You could use sets:

x_dx = {(x, sum(alecproduct.find_factors(x)) - x) for x in range(10 ** 4)}
x_dx = {t for t in x_dx if t[0] != t[1]}
dx_x = {(t[1], t[0]) for t in x_dx}

amicable_pairs = x_dx & dx_x

As in 6502's answer, all amicable pairs are extracted twice. A way to remove these 'duplicates' could be (although it's certainly a mouthful):

amicable_pairs_sorted = {tuple(sorted(t)) for t in amicable_pairs}
amicable_pairs_ascending = sorted(list(amicable_pairs_sorted))

Upvotes: 0

Subbi reddy dwarampudi
Subbi reddy dwarampudi

Reputation: 1097

iterating through keys and values of your sums dictionary to create a new list with all the amicable numbers solves the problem, here is the code snippet.

amicable_list=[]
for i in sums.keys():
    if i in sums.values():
        if (sums.get(sums.get(i,-1),-1) == i) and (i != sums[i]):
            amicable_list.append(i)

Upvotes: 0

R. Bentley
R. Bentley

Reputation: 24

This code should give you a list of all keys that are also values.

my_test = [key for key in my_dict.keys() if key in my_dict.values()]

You don't need .keys() because, this is the default behavior however, I wanted to be explicit for this example.

Alternatively, a for loop example can be seen below.

for key, value in my_dict.iteritems():
    if key == value:
        print key # or do stuff

Upvotes: 0

6502
6502

Reputation: 114481

Your problem is almost solved already... just get all couples out:

for x in my_dict:
    y = my_dict[x]
    if my_dict.get(y) == x:
        # x/y is an amicable pair
        ...

note that every pair will be extracted twice (both x/y and y/x) and perfect numbers (numbers that are the sum of their divisors) only once; not sure from your problem text if 6/6 is considered an amicable pair or not.

Upvotes: 1

Related Questions