Biggest remainder of numbers from 1 to n.

[FraNNNkie]

Hello! It's my first time posting on this forum. I have started programming in september, so I am a noob. My problem is : I have to make a program which will find the sum of the biggest remainders, of the numbers from 1 to n, divided by the numbers from 1 to n...I don't really know how to explain it, because english is not my native language...I will give an example ...if I read the number 3 in the console or in a text file or something...it needs to show 1, because the biggest remainder of 1 is 0, the biggest remainder of 2 is 0, and the biggest remainder of 3 is 1 (0 + 0 + 1 = 1). So, I worked out..what I should do, the code kinda works, but I have a stupid time restriction and, of course, I exceed it. The time limit is 0.1 seconds...which for my code is only available for small numbers. I tried online and on the forum, but I couldn't find anything. I think there's gotta be a formula or something.

My code:
/***FraNNNkie***/
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream f("biggest_remainder.in");
ofstream g("biggest_remainder.out");
int n, x, remainder = 0, biggestremainder = 0, i, j;
unsigned long long sum = 0;
f >> n;
for(i = 1; i <= n; i++)
{
x = i;
for(j = 1; j <= x; j++)
{
if(x % j > 0) remainder = x % j;
if(remainder > biggestremainder) biggestremainder = remainder;
}
sum = sum + biggestremainder;
}
g << sum;
}

[lastchance]

(Unless I've completely misunderstood what you are saying ... )

Suppose you write down the numbers in order and their biggest remainder (the largest integer strictly less than half that number).

Number        Greatest remainder       Cumulative sum
   1                         0                                    
   2                         0
   3                         1                        1
   4                         1                            2 * ( 1 )
   5                         2                        2 + 2 * ( 1 )
   6                         2                            2 * ( 1 + 2 )
   7                         3                        3 + 2 * ( 1 + 2 )
   8                         3                            2 * ( 1 + 2 + 3 ) 
   9                         4                        4 + 2 * ( 1 + 2 + 3 ) 
  10                         4                            2 * ( 1 + 2 + 3 + 4)

Do you spot the pattern?

Now you can deal separately with odd and even cases, noting that there is a formula for
1+2+3+4+ ... + M (just the average value times the number).

Input n: 1000000000
Sum of biggest remainders is 249999999500000000

[FraNNNkie]

Thanks, lastchance, I got it to work.
This is the final code:
/***FraNNNkie***/
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream f("biggestremainder.in");
ofstream g("biggestremainder.out");
long long n;
unsigned long long sum = 0;
f >> n;
if(n % 2 > 0) sum = n / 2 + (n / 2 - 1) * (n / 2);
else sum = (n / 2 - 1) * (n / 2);
g << sum;
}

[lastchance]

@FraNNNkie,

Your code does work (I think), but not in an ideal manner. For the case of n odd, n/2 will, because of integer division, actually produce (n-1)/2. This turns out to give the correct answer, but it is far from obvious in the coding.

I think the algebraic formulae are better written:
- if n is odd, sum = (n-1)*(n-1)/4
- if n is even, sum = n(n-2)/4

Noting the odd or even status, neither will undergo the rounding down associated with integer division.

#include <iostream>
#include <fstream>
using namespace std;

typedef unsigned long long INT;

//============================

INT input()
{
   INT n;

// ifstream in( "in.txt" );            // file input, when required
// in >> n;
// in.close();

   cout << "Input n: ";                // console input alternative
   cin >> n;

   return n;
}

//============================

void output( INT sum )
{
// ofstream out( "out.txt" );          // file output
// out << sum;
// out.close();

   cout << "Sum of biggest remainders is " << sum << endl;
}

//============================

int main()
{
   INT n = input();
   INT sum;
   
   if ( n % 2 == 0 ) sum = n * ( n - 2 ) / 4;             // even case
   else              sum = ( n - 1 ) * ( n - 1 ) / 4;     // odd case
   
   output( sum );
}

[FraNNNkie]

Thank you very much.