₦airaland Forum

kudaisi:
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Full, working program here: http://ideone.com/0S6NVj
Largest value at index: 503
Sequence is: 9 x 7 x 8 x 1 x 7 x 9 x 7 x 7 x 8 x 4 x 6 x 1 x 7 = 2091059712

[s]Runtime: 0.000199762 seconds;
Memory: 3.28MB[/s]

deleted!

kudaisi:
The sum of the squares of the first ten natural numbers is,

12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Python 2.7x
>>> (50*(2+99))**2 - reduce(lambda x, y: x + y**2, range(101))
Ans: 25164150
One liner ...:-) .... The magic values to the left of the subtraction are from the AP series summation formula

olyjosh:
Thanks for reminding me of Sieve of Eratosthenes. That will work fine for the example test case but not for natural number that is as big as 600851475143, it wont work in java since the largest lenght of array or Set(and Set implementation) you can have is 2^31 (int precision) and Sieve of Eratosthenes reqires boolean flagging over such array.

Sieve of Eratosthenes is actually the best for this problem. A colleague of mine pointed that out to me. It works in 0.01 seconds on my PC. C++.
Checkout:
http://ideone.com/n0CVvD
...

olyjosh:
@WhiZTiM check this out
Runs for 10seconds on 4gb RAM, 1.65GHz Duo Core processor

public class Primes
{
    static boolean isPrime(long n)
    {
        if ( n % 2 == 0 )return false;
        long sqrt = (long) Math.sqrt(n);
        sqrt= sqrt%2 == 0 ? sqrt-1 : sqrt; 
        for ( int i = 3; i < sqrt; i += 2 ) 
        {
            if ( n % i == 0 )return false;
        }
        return true;
    }
    
    public static void main(String[] args)
{

    long t = 600851475143L;
    long d = 2;
    while (1==1)
    {
        long tmp = 600851475143L / d;
        if ( t % tmp == 0 &&  isPrime(tmp) )
        {
            System.out.println("= " + tmp);
            break;
        }
        d++;
    }
}
}

The division sequence....
A bit more clever solution! +1.

olyjosh:
public class LargestPrimeFactor {
static boolean isPrime(long n){
if(n==1)return false;
if(n==2)return true;
if(n%2==0) return false;
int max = (int)Math.sqrt(n);
for (int i = 2; i <= max; i++) {
if(n%i==0)return false;
}
return true;
}

static Queue<Long> factors(long n){
Queue fac = new ArrayDeque();
//ArrayList<Long> factors = new ArrayList<>();
long h=Math.round(n/2);
for (long i = 2; i <= h; i++) {
if(n%i==0){fac.add(i);}
}
return fac;
}

public static void main(String[] args) {
long lastPrime=0;
long n =600851475143L;
Queue<Long> factors = factors(n);
for (Iterator<Long> iterator = factors.iterator(); iterator.hasNext() {
long next = iterator.next();
if(isPrime(next))lastPrime=next;
}
System.out.println("largest prime factor is: "+lastPrime);
}
}


largest prime factor is: 6857
This solution got me scared cause it runs for about 2minnutes on my 4gb RAM, 1.65GHz processor

Nice... simple and elegant.

We could do a little more better... ...requires more code though...

Still a bit of a DP problem... My implementation (inefficient) works in about 11.78seconds
On my PC, a 1.7Ghz CPU (Core i5 4210U).

On an interesting note, I ported the implementation to Python... and its been running for the past 15 minutes! ...I am still yet to get an answer.
. . ..lolz. ... ...Despite using C array type... I can only offer sympathy to what Ruby will be like....

...ok, here's it
http://ideone.com/6Iu0fJ (13.44 seconds)

Edit: See the efficient version in my next comment https://www.nairaland.com/2286523/trivia-coding-questions-euler-project/1#33393053

olyjosh:
Thanks for reminding me of Sieve of Eratosthenes. That will work fine for the example test case but not for natural number that is as big as 600851475143, it wont work in java since the largest lenght of array or Set(and Set implementation) you can have is 2^31 (int precision) and Sieve of Eratosthenes reqires boolean flagging over such array.

...oh right... You guys don't have bitarrays in Java? ...Ouchhh
....Another optimization (rough thought) ... Its quite expensive, but you can split up the generation process. Generate them in chunks: then restart using higher values...
First 30 primes, next 30 primes, next 30 primes... ...and so on.... so, after 90, for example.

You can order this 90, and when a search for prime is needed, just do a binary search on this 90.
(easier said than done, #haha)

Comparing the Runtime of olyjosh's simple and elegant solution, (Java) with mine, (Python)
You can see some abominable things happening... Python 3x faster than Java. ....HOw?
Memorization. ....

http://ideone.com/XNVT5m ....Java (greedy) ...0.07seconds 320MB
http://ideone.com/VSTUQe .....Python (Dynamic Programming) ...0.02seconds 8MB

Java will regain its glory if DP/Memorization is used.

Nonetheless...
Fibonacci Solution.... 4000000 max....

"""Very Fast reusable and Dynamic Fibonacci calculator """
class Fibonacci:
	def __init__(self):
		self.memory = [0, 1, 1]
	def compute(self, n):
		if n < len(self.memory):
			return self.memory[n]
		c1 = self.compute(n - 1)
		c2 = self.compute(n - 2)
		self.memory.append(c1 + c2)
		return c1 + c2

def solve(limit):
	fib = Fibonacci(); rtn = []
	for x in range(limit):
		n = fib.compute(x)
		if n > limit: return rtn
		if n % 2 == 0: rtn.append(n)

sum(solve(4000000))

Answer: 4613732
http://ideone.com/VSTUQe



....em off for the Day.

olyjosh:
largest palindrome made from the product of two 3-digit numbers.

    static boolean isPalindrome(String s){
        return new StringBuffer(s).reverse().toString().equals(s) ;
    }

Lovely implementation. Looks quadratic, but it works very well for small values of n; Kudus.
I think you should prefer StringBuilder instead of StringBuffer for this case... I am not much of a Java guy, so don't take my advice seriously. :-).

--> Ideone shows same time, but slightly less memory consumed, which quite frankly, is irrelevant (5KB) .... http://ideone.com/PRx8qX and http://ideone.com/n4H8rL

For Largest prime number, my blind guess goes this way...

For a number, say X;

1. Generate prime numbers with values up to or greater than X;, say P0, P1, P2 ... Pn
2. if Pn == X, then return Pn; ...else
3. You in in deep sh!t ....Combinatorics.... Here we come! :-) ...or
4. Actually, find the largest value of P that divides X completely... ...i.e X % P == 0;
5. let Y = X / P, find the next largest value from Pn that divides Y...

...silly, I know... Will try and update this and implement soon.
::Please bear with me kudasi, I will really love to try my hands on these things and refresh/resharpen my brain a bit. ...and most importantly, learn. ...So much on my hands, will modify my posts (transform them to my attempted solutions), hopefully before Monday.


@olyjosh.
I am really impressed! ...Would love to chat up with you Sir.

For the Fibonacci problem...
You may want to use some form of Dynamic Programming....

Example: ..(WARNING: Not tested!)... The member initialization is a C++11 language feature.

class Fibonacci {
	std::vector<uint64_t> memory{0, 1};
public:
	uint64_t compute(unsigned index){
		if(index < memory.size())
			return memory[index];
		uint64_t c1 = compute(n - 1);
		uint64_t c2 = compute(n - 2);
		memory.push_back(c1 + c2);
		return c1 + c2;
	}
};

. . . .Happy Coding ....
. . .As for the prime number generation, you may want to try Sieve of Eratosthenes... or other Primality tests...

...my favorite, "...most prime numbers from 3 and above obeys ....(6k + 1) or (6k - 1), where k is a natural number"... THat should speed up implementation to some extent....

Let us park two spaces ...to post solutions later... :-)
- - - Forgive me, can't think now... :-)

EDIT 1: After solving some questions(below this post and next page), I thought I rearrange some workings into a cheatsheet.
Will update it when the need arise, or when time permits...
http://ideone.com/NqHgtM

Interesting... PDP = APC; APC = PDP;

#babaonechance. I am hopeful Nigeria will be great.

If this thread is not closed, somebody will trek from Sokoto to Calabar

Quips aside,
I didn't read the threads, but I know NL is somebody's business. So, the proprietor may choose to be "undemocratic in our purview" at any point in time. No questions.

The proprietor, seun, I believe, has so much on his desk daily, he can't and is not expected to spend much time trying work this out with everyone...
. . . . Quite frankly, ask the moderators of this section who are practically doing nothing to make it engaging. They rarely post a topic or comment. And that is simply a very poor attitude; No matter how much "amateur" most posts are.

Wow

teufelein:
this must be a joke of the century..mallam [size=18pt]gej[/size], an imbecilic, a clueless and a dimwitted baboon from the zoo nigeria to become what..? i've forgotten...? inquiring mind wants to know.

Awww... Kpele. Sorry oh. Accept my sympathy. Its evident that you are not loved by anyone. You are so sad....

EDIT: Your thought system betrays every iota of wisdom in fool. And that's sad...
Mehnnn.... You are sooo sad.

Well, stop insulting GEJ if you want to be happier.

I may not be able to mention them point blank but... Forgive me to just beat the bush...

For Business...
Royal Dutch Shell and its subsidiaries have a massive deployment of Microsoft products.
With massive use of SharePoint and Lync. I must say that, they are ideal for a large company.

For Technical...
They use many proprietary software. Some popular ones includes an array of AutoDesk products. Another used to monitor production and systems parameters is from OSISoft
A lot are unpopular to the average computer user.

There are lots of Embedded systems that are deployed on the field. The company has a globally large and competent IT staff.

Most software are not in-house. Neither are they locally contracted. There is a global standard and continuous efficiency review of their Software infrastructure. Additionally, as one of the frontiers in the Energy industry, the standard and reputation of their contractors matters to them. Likewise Software security.

The company has several thousands of volume licensed Software that is easily accessible to staff... For staff, right from their desk, they request... if approved, it's installed over the company's intranet.

They adopt some of the latest software and tech. But it must first go through some intensive change process that involves lots of stakeholders including Technical Authorities. For global adoption, the stakeholders cut across many different countries and Contractors... And all these have varying opinions. So you see its not so easy to just adopt a software.

They consider seamless integration with existing data and tools. It mustn't fail.

...
I hope this helps.

Politicians... Do they have a religion?

Lovely

EggovinMma:


SHOIRRRRRRRR!
UNA STILL DEY RAPE UNA SELF JOIN??
NA EVERY HOLE UNA DEY C ENTER? ? ANIMALISTIC ANIMALS.
I AM NOT SURPRISED THO, AFTER ALL UNA DEY FUCCCK GOATS, COWS, AND ANY ANIMAL THAT HAS ANY KIND OF HOLE



Waiting for the animals to bash me.

I am sure you are on that list of yours... ..i.e "GOATS, COWS, AND ANY ANIMAL ...." ... I suspect you are in the breed of Goat or Cow....
....

This is really serious ....

@OP, nice...
....the previous one on DPKG though... its mostly applicable to Debian based Distros. RedHat uses RPM

Want to start an App or command and detach it from the terminal,
example "gedit"
yourname@yourPC:~$ gedit & disown

Having directory ownership problems, including permission to Read/Write/Execute.
yourname@yourPC:~$ chown yourname:yourname directory_name -R ..."-R" makes it recursive

Having directory permission problems to Read/Write/Execute.
yourname@yourPC:~$ chmod +xrw directory_or_file_name -R ..."-R" makes it recursive. "x" executable. "w" writable. "r" readable

Deny Read/Write/Execute.
yourname@yourPC:~$ chmod -xrw directory_or_file_name -R ..."-R" makes it recursive. "x" executable. "w" writable. "r" readable

Need help with a command?
yourname@yourPC:~$ man command_name

Need to read things one screen view at a time, pipe it to more
yourname@yourPC:~$ command | more

...Hundreds more of essential commands....
My advice is, don't try to cram them all... Just understand how to read man pages first...
You will flow with the commands over time and with experience....
:About Me: longtime Linux User....

Sequel to a request on this post, https://www.nairaland.com/2216760/simple-c-codes-still-confuse-me#32101262
I thought it good to reply with a new post, so that a wider community of people can learn.
#####
Hopefully, this post/reply is brief, concise and not too technical. (experienced programmers too will gain something)
#####
#####
===== FUNCTIONS and STACK======

----------- A small picture --------
Consider a man named Musa who has to execute some tasks; those tasks are fully wrapped in a box. (Think of each box like a portable version of your local Grinding Machines/Blender where you grind Tomatoes, maize, etc; You know there are different kinds, sizes, and types of grinding Machines, so are there different type of boxes ).

Musa is in a warehose full of Boxes; Now There is long enclosed rail with only one end accessible to Musa where he can push Boxes to, if he wishes; Each box cannot work on its own without a power supply; And the only power supply is at the end of the rail, where Musa sits.

-----Relating the above.....------

Your program starts from the function "main"; in this case, You have given Musa a box to process;
Musa, places the Box on the end of the rail, plugs it and starts processing it. At some point, He reaches a point where he cannot proceed without the result of another function(Box); He then stops there; but He is given some data (lets say Tomatoes) to call the other function with;

Musa unplugs "main" and pushes it further into the rail... then gets up and walks through the warehouse in search of the Box he needs to proceed. He retrieves it and brings it to his desk; Lays it on the end of the rail. remember, "main" has been pushed further into the rail. He plugs the new function(box) into the power supply, pours the Tomatoes into it and starts processing....

If He reaches a point where he needs, another function to proceed, ...then the entire process is repeated until the functions starts returning (i.e a function executed to completion)...
When a function is returning... Musa collects the results(lets say result of grinding tomatoes and onions); then He cleans up that machine(Box). Unplugs it and returns it to the warehouse floor. He then rolls the rail forward until the last Box He was using pops out. He connects it, and continues from where He stopped, this time with the results of the previous function. Hence, he can proceed. :-)

Now, that my friend, is a function and a stack. !
The rail, is your stack, the boxes are your functions!

When we are returning from a function(cleaning up the machines), Destructors of objects are called. (In C++ and D).
We can simply view a stack as part of your RAM that is grows and shrinks with respect to function calls;

======= Extras ========
- There is something called stack unwinding. This simply means the minimum work you must do to remove boxes from the rail.
- There is something called stack overflow. This simply means having too much items on your rail to extents that it's full, therefore, preventing you to push more boxes into it.
- When a program is multi-threaded, it means, you have multiple Threads(box rails) and Executors(Musa)
- Functions may be inlined, meaning boxes embedded in boxes, thus Musa, doesn't have the burden of going to look for it.
- Every program starts with a function. (some may be in a global disguise, like scripting languages)

======= Technical =======
- Functions are fast because, every variable inside is addressed in a very simple fashion; relative offsets;
The CPU simply reads from direct offsets in order to retrieve the value you want to read;
Interestingly, (most at times) the data doesn't need to be re-read from RAM, because while the function is fetched, the entire function block will (almost always) be fetched from RAM into the CPU's memory(cache).

- One key difference that makes C++ faster than Java(not always); and Java faster than Python(not always) is in the way they resolve their functions;

- C++ knows exactly where the function is at every call site. and calls them directly (non virtual functions);
- Java looks the function up in a Virtual table (jumps to an offset, to find the exact position of the function);
- Python looks up a dictionary, does some calculations, and jumps to the function's call site

Note: These are traditional ways these languages work. But on good days (most of the time), they are able to make direct calls, hence as fast as C++;

If You are REALLY interested in the ADVANCED stuff, head to http://en.wikipedia.org/wiki/Call_stack ...start from there and dig in deeper.

==============
From a Machine's point of view, a function is basically any well defined cluster of (instruction and data).
What I mean is, A function is an executable region in memory.
==============

Congrats to our dear Nation Nigeria, on her Presidential Elections.

Regards,
Timothy

[center][/center]

Javanian:
LMAO Nice one
But I don't think it is non deterministic, I beleive non determinism means multiple possible transitions/outputs on a particular input. It doesn't make it random.

True. Computers are fairly deterministic.
My premise for the post was that, aggregating PHCN power supply state at any point in time, t in every location, L will likely result in values with some degree of stochastic characteristics; ....(I am a Maths enthusiast , but not a crypto expert )

Its not a serious topic; but you can get multiple outputs with in stateless system.

danvery2k6:
I don't understand. What has PHCN got to do with PRNG? am I missing something here?

Don't mind me ohh.... I thought o being a bit silly....

crotonite:
thank you man. are you a proffessor or what?
anyway i have never come across such a superb explanation of array and pointers before. wow so easy to understand.
pls can you explain for me stacks and function calls when your chanced?

You are very much welcome.
Nope, I am not a Professor (at least, not yet). :-)
I am just a Systems guy...

crotonite:
anyway i have never come across such a superb explanation of array and pointers before. wow so easy to understand.
pls can you explain for me stacks and function calls when your chanced?

Sure... I will.
EDIT: I have.. please see: https://www.nairaland.com/2232875/simple-explanation-functions-stacks

crotonite:
I have an advice/request for you, I know this seems nonsensical but there is always a sense in every nonsense.
the way you explained the above topic shows that you have something special that I have not come across for a long while. please would you mind if I name you the 'king-of-abstractions' on nl?

...hehe... It's not nonesense. ... But How can I be King of Abstractions when there is no kingdom? ...that will be akin to King Julien in "Penguins of Madagascar" ...lolz

crotonite:
let me get to the point, would you mind putting down some tutorials or if possible a textbook for nigerian aspiring coders? something like the 'for dummies serries'. but I think it can be called 'coding for akpos!' it could be of any lenght but with time it can be improved. bros you can touch so many lifes I tell you.
Thank you and God bless.

Well, Thanks for the suggestion.

jamex93:
PDP dogs at work


R.I.P to the death

sai buhari

Indeed... ...common sense is rare..

Interesting...

We should only wait for inec. Nobody's twitter handle or collation will be accepted here....

SAVEDBABA:
pls can u teach me programming on "c" and if possible "matlab"

Well, I don't know how that will work, cause I think there are so many resources available online...
...Not only I, but so many great people here can provide you with pointers... so, you are always welcome to ask...

crotonite:
//how about passing a 2d array to a function?

void take2DArr( int arr[][]){

// this doesn't compile whatz wrong

}[/color]

how is the right way to pass a 2d array to a funtion?

Well, codemarsharl08 is right. But just to expand more,

The size of C++ arrays must be known at compile time. (except for heap allocated arrays);
For every function you call, the CPU must do two things:

1. fetch the address of the function (just like a variable)
2. fetch the function's stack size; (think of it like a block of memory which represents your entire function)


There are of cause different ways the compiler may transform function arguments, but the point here is that, once you compile your program, a function's stack size NEVER changes. (Mainly because of caching -> hence insane execution speed in tight loops). ..and of cause Inlining

When compiling, the compiler must resolve the sizes of all functions, including the arguments;
When you pass a 1D array,

void take1DArray(int arr[]);
//the compiler transforms the above call to:
void take1DArray(int* arr);


This is because, for any expression, an array is permitted to implicitly decompose ONLY once!.
Array decomposition is basically the transformation of an array to a pointer;

The syntax "typename Type[]" is a declaration of a variable length array and is exactly the same as "typename* Type".
Hence, "int arr[]" is same as "int* arr";

Do you know that whenever you declare an array like this,

{
int arr[] = {1, 2, 3, 4, 5};
//or
int arr[5] = {1, 2, 3, 4, 5};
}

Within its declaration scope( '{' and '}' ), "arr" still has a its 'size' property. Hence for that reason, "sizeof(arr)" will always give you the total size of the array;

When you pass "arr" to any function, that property implicitly disappears. Hence, "arr" is decomposed.
Example
void take1d(int arr[])
{
//blaa blah blah
sizeof(arr); ...gives you size of a pointer, same as sizeof(arr*)
}

void take1D(int arr[3])
{
//blaa blah blah
sizeof(arr); ...gives you size of a pointer, same as sizeof(arr*)
}

int main()
{
int arr[] = {1, 2, 3, 4, 5};
sizeof(arr); ...gives you the lump size of 5 ints
}




========Now, what about 2D arrays and above=========
Exactly the same thing applies!

You have 4 choices:

void take2D(int** arr, int sz1, int sz2);
void take2D(int* arr[], int sz1, int sz2);
void take2D(int arr[][5], int sz1, int sz2);
void take2D(int arr[5][5], int sz1, int sz2);

...they are all the same. just syntactic sugar; The last two will probably help only in bounds checking

...Now, back to our previous discussion on Function Size:
The Compiler must know the size of a function. But all array parameters in a function are implicitly pointers;

In any context, the compiler is only allowed to perform implicit operations once! ...whether, implicit conversions, construction, etc;...
In doing "int arr[][] ...", you are asking the compiler to perform implicit operations of decomposition or calculating more than once!... this breaks it's Automata and design principles. There may be other better reasons though.

========Etcetera=========
There are current efforts for function stacks to be variable at runtime.
This involves a lot of compiler intricacies, and machine-code injection by the C++ runtime;
Variable stack is the foundation to a new container that didn't make it into the C++11 and C++14 standards. --> std::dynarray;

The ISO C++ committee voted it out, partly because the proposed algorithm wasn't as fast as a native function call. And it required deep intricate support from compilers and its runtime. Though intensive efforts are being made to improve it and have it acceptable... Hopefully by C++1y, (C++17).

....whew... that was one hell of an explanation! ....(Well, I was a bit jobless, and felt I could write something... :-) )
Perharps, I should turn this comment into a new thread?

...regards,
Timothy

Sadly we are blinded to see reality of things....
... imagine the riot that will happen if GEJ is returned to power...
If GEJ is returned, I assure you, these same people will start destroying lives and properties within their land...
I wish they are "civilized and peaceful" in their response to failed expectations.