What programming language you start with really all depends on where you want to go with programming/coding. The great thing about this field is that there are an absolute abundance of smaller fields that you can go into, all using programming in their own unique ways. For web applications, a good start would be with HTML and later moving your way through CSS, JavaScript, JQuery, PHP, SQL, and any of the JavaScript libraries. Ruby is also a popular choice, so I would recommend checking that out too. For more scientific fields or areas with more machine learning and A.I., Python is generally a great place to start as it is widely used in that field of study. C++ is also a very useful language to know for that, but it can be a little more challenging for beginners. For game and application design, languages such as C#, C, Swift, Kotlin, and Java are most often used for that.
Background
The integer complexity of a positive integer is the minimum possible sum of the numbers used in an expression - using only positive integers, addition, multiplication, and parentheses - that's equal to the given number. See this week's Intermediate challenge for examples and more information.
The typical definition of integer complexity disallows all numbers in the expression other than 1. This definition is equivalent, so either one you want to use is fine.
As far as I know, efficiently determining the integer complexity of a given number is an open question. Your challenge is to provide as tight an upper limit as possible for a particular input.
Challenge
Post an expression equal to 12345678910111213 - using only positive integers, addition, multiplication, and parentheses - such that the sum of the numbers in the expression is as small as possible.
Here's one example:
1+4*3*3*3*(1+4*4*(1+3*(1+3*(1+5*3*3*(1+5*4*4*2*(1+4*3*(1+4*4*3*2*(2+5*(1+5*4*3*(1+3*(1+5*3*(2+5*1))))))))))))
If you add up all the numbers in this expression (1+4+3+3+3+...+2+5+1) you get a sum of 122. How much better can you do? When this post is 7 days old, the expression with the smallest sum will merit +1 gold medal flair.
Challenge details
Don't worry about formatting it neatly. Output format doesn't matter as long as you can explain how to make sense of it.
In the event of a tie, also post an expression for 1234567891011121314, 123456789101112131415, etc. I'll break ties by looking at the first sum where your solutions differ.
If you post your solution to this thread, it's fair game for others to work off. You may PM me your solution instead of posting if you don't want people to use them for their own solutions, but it would be great if you also post the sum here so people have a goal to work for. I will verify anybody's claim, so for instance you can comment, "I found an expression with a sum of 118" and PM me the expression, and then I'll reply to your comment saying that I have confirmed that your expression is valid. After 10 days I'll post anybody's solution who PM'd me but didn't post it, so everything will eventually be public.
I reserve discretion to give the award to whoever made the largest contribution to the best solution, if my criterion would technically give it to someone else. But if you feel this is unfair, let me know and we'll work it out.
Solution
in Java
12345678910111213: 114
Full solution:
1 + (3 * 2) * ((3 * 2) * 3) * (1 + (4 * 4) * (1 + ((4 * 3 + 1) * 3) * (1 + (3 * 2) * ((4 * 2) * (3 * 2 + 1) + 1) * (1 + ((5 * 2) * (4 * 2)) * ((4 * 3) * (3 * 2 + 1) + 2) * ((4 * 3) * (4 * 2)) * (1 + (3 * 3) * ((5 * 2) * (3 * 3)))))))
1234567891011121314: 127
Full solution:
(3 * 2) * (1 + (3 * 2) * (3 * 3) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * (4 * 2)) * (1 + ((3 * 2) * (3 * 2)) * (1 + ((3 * 2) * 4) * ((3 * 3) * (3 * 3)) * (1 + ((3 * 2) * 4) * (1 + (4 * 2) * ((5 * 2) * (4 * 2)))))))))))
123456789101112131415: 142
Full solution:
(5 * 3) * (1 + ((4 * 2) * 5) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * (4 * 2)) * (1 + ((3 * 2) * (3 * 2)) * (1 + ((5 * 2) * (3 * 3)) * ((4 * 4 + 1) * 4) * ((3 * 3) * 3) * (1 + ((5 * 2) * (3 * 3)) * 2)))))))))
12345678910111213141516: 158
Full solution:
(1 + ((4 * 3) * (3 * 2 + 1) + 1) * (3 * 3) * (1 + ((5 * 2) * (3 * 3)) * (1 + ((5 * 2 + 1) * (3 * 2)) * (1 + ((5 * 2 + 1) * (3 * 3)) * (((3 * 2) * 3 + 1) * 2) * (1 + ((4 * 3) * (3 * 2 + 1) + 2) * (4 * 4 + 1) * (3 * 3) * (1 + ((4 * 3) * (4 * 2)) * ((3 * 3) * (3 * 2 + 1)) * ((3 * 3) * (3 * 2) + 1) * ((3 * 3) * (3 * 2) + 1) * 3))))))
1234567891011121314151617: 170
Clean solution: 0 + 14979 * (0 + 141 * (1 + 6 * (1 + 72 * (1 + 6921 * (0 + 6 * (1 + 3312 * (1 + 192 * (1 + 5124 * (0 + 10)))))))))
Full solution: ((((4 * 3 + 1) * (3 * 2)) * ((4 * 2) * (4 * 2)) + 1) * 3) * (((3 * 2 + 1) * 2) * (5 * 2) + 1) * (1 + (3 * 2) * (1 + ((3 * 3) * (4 * 2)) * (1 + (((4 * 4 + 1) * (5 * 2 + 1)) * ((3 * 2) * (3 * 2) + 1) + 2) * (3 * 2) * (1 + (((5 * 4 + 3) * (3 * 2)) * ((3 * 2) * 4)) * (1 + ((4 * 4) * (4 * 3)) * (1 + (((4 * 3) * (3 * 2 + 1)) * ((5 * 2) * (3 * 2) + 1)) * (5 * 2)))))))
The integer complexity of a positive integer is the minimum possible sum of the numbers used in an expression - using only positive integers, addition, multiplication, and parentheses - that's equal to the given number. See this week's Intermediate challenge for examples and more information.
The typical definition of integer complexity disallows all numbers in the expression other than 1. This definition is equivalent, so either one you want to use is fine.
As far as I know, efficiently determining the integer complexity of a given number is an open question. Your challenge is to provide as tight an upper limit as possible for a particular input.
Challenge
Post an expression equal to 12345678910111213 - using only positive integers, addition, multiplication, and parentheses - such that the sum of the numbers in the expression is as small as possible.
Here's one example:
1+4*3*3*3*(1+4*4*(1+3*(1+3*(1+5*3*3*(1+5*4*4*2*(1+4*3*(1+4*4*3*2*(2+5*(1+5*4*3*(1+3*(1+5*3*(2+5*1))))))))))))
If you add up all the numbers in this expression (1+4+3+3+3+...+2+5+1) you get a sum of 122. How much better can you do? When this post is 7 days old, the expression with the smallest sum will merit +1 gold medal flair.
Challenge details
Don't worry about formatting it neatly. Output format doesn't matter as long as you can explain how to make sense of it.
In the event of a tie, also post an expression for 1234567891011121314, 123456789101112131415, etc. I'll break ties by looking at the first sum where your solutions differ.
If you post your solution to this thread, it's fair game for others to work off. You may PM me your solution instead of posting if you don't want people to use them for their own solutions, but it would be great if you also post the sum here so people have a goal to work for. I will verify anybody's claim, so for instance you can comment, "I found an expression with a sum of 118" and PM me the expression, and then I'll reply to your comment saying that I have confirmed that your expression is valid. After 10 days I'll post anybody's solution who PM'd me but didn't post it, so everything will eventually be public.
I reserve discretion to give the award to whoever made the largest contribution to the best solution, if my criterion would technically give it to someone else. But if you feel this is unfair, let me know and we'll work it out.
Solution
in Java
12345678910111213: 114
Full solution:
1 + (3 * 2) * ((3 * 2) * 3) * (1 + (4 * 4) * (1 + ((4 * 3 + 1) * 3) * (1 + (3 * 2) * ((4 * 2) * (3 * 2 + 1) + 1) * (1 + ((5 * 2) * (4 * 2)) * ((4 * 3) * (3 * 2 + 1) + 2) * ((4 * 3) * (4 * 2)) * (1 + (3 * 3) * ((5 * 2) * (3 * 3)))))))
1234567891011121314: 127
Full solution:
(3 * 2) * (1 + (3 * 2) * (3 * 3) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * (4 * 2)) * (1 + ((3 * 2) * (3 * 2)) * (1 + ((3 * 2) * 4) * ((3 * 3) * (3 * 3)) * (1 + ((3 * 2) * 4) * (1 + (4 * 2) * ((5 * 2) * (4 * 2)))))))))))
123456789101112131415: 142
Full solution:
(5 * 3) * (1 + ((4 * 2) * 5) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((3 * 3) * (3 * 2)) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * 4) * (1 + ((4 * 2) * (4 * 2)) * (1 + ((3 * 2) * (3 * 2)) * (1 + ((5 * 2) * (3 * 3)) * ((4 * 4 + 1) * 4) * ((3 * 3) * 3) * (1 + ((5 * 2) * (3 * 3)) * 2)))))))))
12345678910111213141516: 158
Full solution:
(1 + ((4 * 3) * (3 * 2 + 1) + 1) * (3 * 3) * (1 + ((5 * 2) * (3 * 3)) * (1 + ((5 * 2 + 1) * (3 * 2)) * (1 + ((5 * 2 + 1) * (3 * 3)) * (((3 * 2) * 3 + 1) * 2) * (1 + ((4 * 3) * (3 * 2 + 1) + 2) * (4 * 4 + 1) * (3 * 3) * (1 + ((4 * 3) * (4 * 2)) * ((3 * 3) * (3 * 2 + 1)) * ((3 * 3) * (3 * 2) + 1) * ((3 * 3) * (3 * 2) + 1) * 3))))))
1234567891011121314151617: 170
Clean solution: 0 + 14979 * (0 + 141 * (1 + 6 * (1 + 72 * (1 + 6921 * (0 + 6 * (1 + 3312 * (1 + 192 * (1 + 5124 * (0 + 10)))))))))
Full solution: ((((4 * 3 + 1) * (3 * 2)) * ((4 * 2) * (4 * 2)) + 1) * 3) * (((3 * 2 + 1) * 2) * (5 * 2) + 1) * (1 + (3 * 2) * (1 + ((3 * 3) * (4 * 2)) * (1 + (((4 * 4 + 1) * (5 * 2 + 1)) * ((3 * 2) * (3 * 2) + 1) + 2) * (3 * 2) * (1 + (((5 * 4 + 3) * (3 * 2)) * ((3 * 2) * 4)) * (1 + ((4 * 4) * (4 * 3)) * (1 + (((4 * 3) * (3 * 2 + 1)) * ((5 * 2) * (3 * 2) + 1)) * (5 * 2)))))))
Comments
Post a Comment