# Shortest Python 3 for sum of arithmetic progression

Input: from STDIN number of vertices in Graph $$\2 \leq N \leq 100\$$.

Rules: [Code size] = max ([code length without spaces, tabs and newlines], [total code length divided by 4])

Math formulation: In the graph of N vertices, between each pair of vertices can be 3 road states:

• there is a road from A to B
• there is a road from B to A

Find the number of different graphs on given vertices.

We can apply next formula (number of different road states in pow of pairs number): $$\huge3 ^ {\frac{n(n - 1)}{2}}$$.

# My Python 3 37 bytes solution here:

n = int(input())
print(3 ** ((n ** 2 - n) // 2))


I know that exists 34 bytes solution. Then I started to think about 1 liner, and find next formula for sum of arithmetic progression, which use N only once: $$\frac{(2n - 1) ^ 2}{8} - \frac18$$

Unfortunately the code only increased:

x = 2 * int(input()) - 1
print(3 ** ((x ** 2 - 1) // 8))

• This is not enough, but n**2 = n*n. Jul 7, 2020 at 10:17
• If someone knows how to make inline latex formula, pls edit my question. I don't know why it's not working here. Jul 7, 2020 at 10:18
• @mypronounismonicareinstate I looked at this formula for 3 hours and did not see an elephant, thank you. Jul 7, 2020 at 10:21
• Note that your 2nd formula can be turned into a 38-byte one-liner. But of course, that's still too long. Jul 7, 2020 at 10:50
• @Arnauld I think you can remove the -1 too, but 36 bytes is still too long.
– xnor
Jul 7, 2020 at 11:51

# Python 3, 34 bytes

print(3**sum(range(int(input()))))


Try it online!

In Python 2 this is just print 3**sum(range(input())) for 28.

• Why does this answer have five times as many upvotes as mine? (I think they're mostly the same) Am I doing something wrong? (note: the question I am trying to ask is not "where are my upvotes" but "what am I doing wrong or what can I do better") Jul 8, 2020 at 2:19
• I posted this because it was a one-liner, which OP said they started thinking about. I'm not sure why it has so many more upvotes as I would not class this as a "better" code-golf solution (given the altered scoring mechanism), just an alternative one. You've certainly done nothing wrong. Jul 8, 2020 at 11:48

# Python 3, 34 bytes (not counting the newline)

Uses the conventional formula for the sum of the arithmetic progression ($$\\frac{n(n-1)}2\$$) and the trick that n-1 = ~-n (but with higher operator precedence). This way, one pair of parentheses can be omitted.

n=int(input())
print(3**(n*~-n//2))


Try it online!

• Is it possible to get real binary representation of -n? How many bits it use? Because for n = -6, bin(n) give me '-0b110'. I'm trying to understand how is it working. Jul 7, 2020 at 10:41
• @Evgeny You may want to read the Wikipedia article on two's complement. Flipping all bits of n simply results in -n-1. (of course, that's what flipping all bits does in languages with machine-word-sized integers, but in many other languages ~ has the same behaviour) Jul 7, 2020 at 10:46
• Tank you. It's impossible to solve the problem without this sacred knowledge. Jul 7, 2020 at 10:51
• @Evgeny Is Python 3 mandatory? Based on your question title I assume it is, but if not, this could be 2 bytes shorter in Python 2 (print a instead of print(a) and / instead of // which uses integer division implicitly on integers). Jul 7, 2020 at 11:44
• @KevinCruijssen int(...) is also not necessary. (if this is a problem from acmp.ru, like OP's previous question, then Python 3 seems to be mandatory) Jul 7, 2020 at 11:48