In regard to the (2) successful Convair power-plant conversion (GM-Allision 580 & Dart Convair 600-640) program's original operators, it would be North Central (Republic-Northwest) that would have their '580's in service the longest (1988), followed by Frontier Airlines. The 3rd longest serving original operator would turn out to be a bit of a surprise!
Today's Air Algerie dates back to April 1953, when the previous Air Algerie merged with Compagnie Air Transport to form Compagnie Generale de Transports Aeriens-Air Algerie. The new airline had a mixed fleet of DC-3's and -4's and an order for (3) new DC-6B's was placed.
By 1955, Air France had begun taking a financial interest in C.G.T.A. and due to this relationship, the DC-6B order was canceled and (5) 2nd-hand L-749A's were purchased from Air France.
By early 1956, the Constellations were linking several Algerian cities to such destinations as Paris, Marseilles & Toulouse.
Though the future of C.G.T.A.-Air Algerie was bright, there was a more serious battle for national independence that was beginning.
Algeria had been given autonomy in 1946 but after France's defeat in Indo-China (Vietnam) in 1954, the war for independence began to increase in intensity.
Having been a French colony since 1830, the end of colonial rule had begun to increase after WW2.
Air Algerie's route expansion was solely controlled by the French government, who allocated the trans-mediterranean service. In 1957, Air Algerie added (3) Nord 2501 Noratlas's to the fleet and in 1958 placed an order for (3) Sud Caravelles, the 1st arriving in 1960.
Along with the 1st Jets, the Air Algerie crews got a makeover!
The new uniforms had a distinctive look with an obvious French influence. With the arrival of the Caravelle 3's, the airline began Jet service from Oran to Paris ([4] times a week), Bonn to Paris ([2]) & from Algiers to Paris ([13]).
In 1962, Algerian independence was won, at a cost of an estimated 500,000 killed........After it's independence, Algerie began to have a closer relationship with the Eastern-bloc. In 1964, Algerie signed up for several Il-18's but eventually only a single A/C was delivered and used as a VIP plane. By the late 1960's, the Air Algerie fleet consisted of (2) Caravelle 3's, (2) Caravelle 6N's, (9) DC-4's and (3) DC-3's.
By 1968, Air Algerie was looking to upgrade it's domestic route services and decided on an American aircraft (Dart Convair) after a GD-Convair sponsored European Sales tour, to replace the DC-3 but there was a bit of a 'sticky' political problem as Algeria had no relations with the U.S., after it went with the Arab side in the 'Six-Day' War against Israel in 1967, providing 50,000 reserve troops!
Plans for the Dart Convair program actually began back in 1958, as the last 440's were being assembled. The problem was that the current Rolls-Royce power-plants, being used on the Viscounts were under-powered for installation on the Convair airframes. It would be the development of the Dart 542-4 for the NAMC YS-11 that would bring the plans back for the Dart Convair.

Unlike the Allison-GM conversion program, in which Convair just provided future airframe parts, the Dart program had direct involvement at General Dynamics.
A late-build Garuda CV-240 was used as the prototype, as it had been delivered new with the later structural 340 modifications.

An interesting feature of the Rolls-Royce R.Da 10/1 was because of the smaller nacelle width, Convair was able to move the engine centerline (8) inches outboard of the nacelle centerline and still fair the cowling into the existing nacelles at the firewall. This provided more propeller to fuselage clearence and reduced the wing bending in flight.

GD-Convair Ads made it a point of highlighting the Rolls-Royce name to help sales efforts.
Though originally intended for CV-240 customers, as the 240's were not capable of undergoing the Allison-GM '580' conversion, the larger 340/440 airframes were also part of the Dart program, with a slight drop-off in performance due to the increased weight (309 mph vs 300 mph cruising speed).
The Dart Convair conversions were listed as costing $450,000 per A/C, some $200,000 cheaper than the Allison-GM '580'.
For then current CV-240 operators, they would see a 1,000 horse-power increase and a gain of 50-60 mph!
Unlike the "580" conversions, which were all completed in Burbank, CA. by PacAero, the simpler Dart conversions were available to potential customers in kit form (more than half of the Dart Convair conversions would be NOT done at the San Diego, CA. plant!). Both '580' and '600' customers did save money by doing the cabin interior work themselves, increasing their 340/440's to a 56-passenger seating.
Central Airlines signed up for (6) of their 240's plus (3) purchased from GD and Trans-Texas was next, choosing to do their (25) 240's in-house. Caribbean Atlantic Airlines was next with the 1st '640' order.
(sadly, due to the numerous in-house conversions there would be only a few 'official' delivery photos.)
By 1967, as the U.S. conversion orders began to slowdown, GD-Convair decided to send have (2) conversions completed by Aviolanda at the Woensdrecht Air Base in Holland under license agreement. It was hoped that a large number of European 240-440 operators would convert (as it turned out only [7] conversions would be ordered from Aviolanda and [6] from another licensee Scottish Aviation at Prestwick).
Back to Air Algerie, it was the European '600' tour that got their interest but since relations with the U.S. were on the 'outs', the conversions could definitely not be done in the U.S., so the Aviolanda-Holland conversions were the perfect solution! Lufthansa's 340/440's were starting to be sold off as the 737's began to arrive, so (4) were purchased in June 1968 (D-ACAP, -ACEX, -ACUM & -ACIB) and sent to Holland for conversion. What would emerge from the factory was (IMO) one of the best looking of all the '580'-'640's!
Sadly, this is the only known photo of an Air Algerie '640' in it's original color scheme!
As the (4) '640's were delivered they were immediately put to work on Air Algerie's domestic routes (red rectangles).
The '640's were based in Algiers and would take over routes to some of the larger cities such as Algiers-Annaba, Algiers-Ghardiai-In Salah-Djanet-Tamanrasset & Algiers-Oran. There would be (1) International '640' route; Algiers-Palma de Mallorca. By 1970, U.S. relations were beginning to warm, a prelude to the large Boeing order. The 2nd part of the new domestic duo would be from the U.S. but of French design!

(5) Nord '262's were purchased by STA from Allegheny. STA was a third-level taxi operator that flew under the Air Algerie banner (becoming part of Air Algerie in 1974)
The new Air Algerie '262's began ariving in the winter of 1970 and would help to introduce the new color scheme which featured the stylized Swallow on the tail.
The '640's would begin to be re-painted in the new colors also.
Interestingly, the 1970's '640' pilots seemed to have traded in the Dark Blue's for a Khaki non-looking airline look!
The '262's
and the '640's would be the face of domestic operations for Air Algerie throughout the 1970's (a '640' was highjacked in 1970, ending up in Yugoslavia w/o incident-[14] passengers were lost in 1979 in a '262' accident.....)
The (4) '640's would serve the Algerian people faithfully from 1968-1981.

For the Air Algerie Dart Convair '640's, as the 1960's song says "It's been a long strange trip"!..............John3 (Thanks to Chuck Gowing/Airlinecolors.com[RARE '640' image], SDASM-website, Karim23185 Flickr Album, www.npage.de, Flugzeugspotter.de, Airline-Issue-Postcards.npage.de, www.aviation-algerie.com, Air-Britain Photographic Images, www.frenchwings.net, Marcel Legarde[Constellation]. Photographers: Christian Volpati-AirlineFan.com & Pierre Laffargue).